指数検索

指数検索は、ダブリング検索またはギャロッピング検索とも呼ばれます。このメカニズムは、検索キーが存在する可能性のある範囲を見つけるために使用されます。 LとUがリストの上限と下限である場合、LとUは両方とも2の累乗です。最後のセクションでは、Uはリストの最後の位置です。そのため、指数関数として知られています。

特定の範囲を見つけた後、二分探索手法を使用して検索キーの正確な位置を見つけます。

指数検索手法の複雑さ

• 時間計算量： 最良の場合はO（1）。平均または最悪の場合のO（log2 i）。ここで、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:
Item found at location: 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
End

exponentialSearch（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 //increase i as power of 2
      else
         terminate the loop
   done
   call binarySearch(array, i/2, i, key)
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 exponentialSearch(int array[], int start, int end, int key){
   if((end - start) <= 0)
      return -1;
      int i = 1; // as 2^0 = 1
      while(i < (end - start)){
         if(array[i] < key)
            i *= 2; //i will increase as power of 2
         else
            break; //when array[i] corsses the key element
   }
   return binarySearch(array, i/2, i, key); //search item in the smaller range
}

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 = exponentialSearch(arr, 0, n, searchKey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

出力

Enter number of items: 20
Enter items:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
Enter search key to search in the list: 780
Item found at location: 16