二元搜寻
对列表进行排序后，我们可以使用二进制搜索技术在列表中查找项目。在此过程中，整个列表分为两个子列表。如果在中间位置找到该项目，它将返回该位置，否则将跳转到左或右子列表，然后再次执行相同的过程，直到找到该项目或超出范围为止。
二进制搜索技术的复杂性
时间复杂度：最佳情况下为O(1)。O（log2n）用于一般情况或最坏情况。
空间复杂度：O(1)
输入输出
Input: A sorted list of data: 12 25 48 52 67 79 88 93 The search key 79 Output: Item found at location: 5
算法
binarySearch(array, start, end, key)
输入-排序后的数组，开始和结束位置以及搜索键
输出-键的位置（如果找到），否则位置错误。
Begin
if start <= end then
mid := start + (end - start) /2
if array[mid] = key then
return mid location
if array[mid] > key then
call binarySearch(array, mid+1, end, key)
else when array[mid] < key then
call binarySearch(array, start, mid-1, key)
else
return invalid location
End示例
#include<iostream>
using namespace std;
int binarySearch(int array[], int start, int end, int key) {
if(start <= end) {
int mid = (start + (end - start) /2); //mid location of the list
if(array[mid] == key)
return mid;
if(array[mid] > key)
return binarySearch(array, start, mid-1, key);
return binarySearch(array, mid+1, end, key);
}
return -1;
}
int main() {
int n, searchKey, loc;
cout << "Enter number of items: ";
cin >> n;
int arr[n]; //create an array of size n
cout << "Enter items: " << endl;
for(int i = 0; i< n; i++) {
cin >> arr[i];
}
cout << "Enter search key to search in the list: ";
cin >> searchKey;
if((loc = binarySearch(arr, 0, n, searchKey)) >= 0)
cout << "Item found at location: " << loc << endl;
else
cout << "在列表中找不到项目。" << endl;
}输出结果
Enter number of items: 8 Enter items: 12 25 48 52 67 79 88 93 Enter search key to search in the list: 79 Item found at location: 5