指数搜索
指数搜索也称为双倍搜索或疾驰搜索。该机制用于查找搜索关键字可能出现的范围。如果L和U是列表的上下限，则L和U都是2的幂。对于最后一部分，U是列表的最后位置。因此，它被称为指数。
找到特定范围后，它使用二分搜索技术找到搜索键的确切位置。
指数搜索技术的复杂性
时间复杂度：O(1)最好的情况。O(log2i)平均或最坏情况。其中i是存在搜索键的位置。
空间复杂度： O(1)
输入和输出
Input: A sorted list of data: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 The search key 780 Output: 在以下位置找到的物品： 16
算法
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
EndexponentialSearch(array,start,end,key)
输入： 排序后的数组、开始和结束位置以及搜索键
输出： 密钥的位置（如果找到），否则位置错误。
Begin
if (end – start) <= 0 then
return invalid location
i := 1
while i < (end - start) do
if array[i] < key then
i := i * 2 //将i增加为2的幂
else
terminate the loop
done
call binarySearch(array, i/2, i, key)
End示例
#include输出结果using namespace std; int binarySearch(int array[], int start, int end, int key) { if(start <= end) { int mid = (start + (end - start) /2); //列表的中间位置 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 exponentialSearch(int array[], int start, int end, int key){ if((end - start) <= 0) return -1; int i = 1; //作为2^0=1 while(i < (end - start)){ if(array[i] < key) i *= 2; //我将增加为2的幂 else break; //当array[i]与关键元素交叉时 } return binarySearch(array, i/2, i, key); //在较小范围内搜索项目 } int main() { int n, searchKey, loc; cout << "输入项目数： "; cin >> n; int arr[n]; //创建一个大小为n的数组 cout << "输入项目： " << endl; for(int i = 0; i< n; i++) { cin >> arr[i]; } cout << "输入搜索键在列表中搜索： "; cin >> searchKey; if((loc = exponentialSearch(arr, 0, n, searchKey)) >= 0) cout << "在以下位置找到的物品： " << loc << endl; else cout << "在列表中找不到项目。" << endl; }
输入项目数： 20 输入项目： 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 输入搜索键在列表中搜索： 780 在以下位置找到的物品： 16