对列表进行排序后,我们可以使用二进制搜索技术在列表中查找项目。在此过程中,整个列表分为两个子列表。如果在中间位置找到该项目,它将返回该位置,否则将跳转到左或右子列表,然后再次执行相同的过程,直到找到该项目或超出范围为止。
时间复杂度:最佳情况下为O(1)。O(log2 n)用于一般情况或最坏情况。
空间复杂度: 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