指數搜尋演算法

指數搜尋演算法的目標是在輸入陣列的某個範圍內進行搜尋，它假設所需元素必須存在於該範圍內，並在該特定的小範圍內執行二分搜尋。該演算法也稱為倍增搜尋或手指搜尋。

它類似於跳躍搜尋，將排序後的輸入劃分為多個塊並進行更小規模的搜尋。但是，差異出現在計算劃分塊和應用的小規模搜尋型別時（跳躍搜尋應用線性搜尋，指數搜尋應用二分搜尋）。

因此，此演算法以 2 的冪進行指數跳躍。簡單來說，搜尋是在使用 pow(2, k) 分割的塊上執行的，其中 k 是一個大於或等於 0 的整數。一旦位置 pow(2, n) 處的元素大於鍵元素，則在當前塊上執行二分搜尋。

指數搜尋演算法

在指數搜尋演算法中，跳躍從陣列的第一個索引開始。因此，我們手動將第一個元素作為演算法的第一步進行比較。

步驟 1 − 將陣列中的第一個元素與鍵進行比較，如果找到匹配項，則返回第 0 個索引。

步驟 2 − 初始化 i = 1 並將陣列的第 i 個元素與要搜尋的鍵進行比較。如果匹配，則返回索引。

步驟 3 − 如果元素不匹配，則以 2 的冪對陣列進行指數跳躍。因此，現在演算法比較存在於增量位置的元素。

步驟 4 − 如果找到匹配項，則返回索引。否則，迭代地重複步驟 2，直到增量位置的元素大於要搜尋的鍵。

步驟 5 − 由於下一個增量具有比鍵更高的元素並且輸入已排序，因此演算法在當前塊上應用二分搜尋演算法。

步驟 6 − 如果找到匹配項，則返回鍵所在的索引；否則，將其確定為不成功的搜尋。

虛擬碼

Begin
   m := pow(2, k) // m is the block size
   start := 1
   low := 0
   high := size – 1 // size is the size of input
   if array[0] == key
      return 0
   while array[m] <= key AND m < size do
      start := start + 1
      m := pow(2, start)
      while low <= high do:
         mid = low + (high - low) / 2
         if array[mid] == x
            return mid
         if array[mid] < x
            low = mid + 1
         else
            high = mid - 1
   done
   return invalid location
End

分析

儘管它被稱為指數搜尋，但它並非以指數時間複雜度執行搜尋。但眾所周知，在此搜尋演算法中，執行的基本搜尋是二分搜尋。因此，指數搜尋演算法的時間複雜度將與二分搜尋演算法相同，即O(log n)。

示例

為了更好地理解指數搜尋演算法並以更簡單的方式理解它，讓我們使用指數搜尋演算法在一個示例輸入陣列中搜索元素。

提供給搜尋演算法的排序輸入陣列為：

讓我們在給定陣列中搜索元素 81 的位置。

步驟 1

將陣列的第一個元素與鍵元素 81 進行比較。

陣列的第一個元素是 6，但要搜尋的鍵元素是 81；因此，跳躍從第 1 個索引開始，因為沒有找到匹配項。

步驟 2

在初始化 i = 1 之後，將鍵元素與第一個索引中的元素進行比較。這裡，第一個索引中的元素與鍵元素不匹配。因此，它再次以 2 的冪進行指數遞增。

索引遞增到 2^m = 2¹ = 將第二個索引中的元素與鍵元素進行比較。

它仍然不匹配，因此再次遞增。

步驟 3

索引再次以 2 的冪遞增。

2² = 4 = 將第 4 個索引中的元素與鍵元素進行比較，但尚未找到匹配項。

步驟 4

索引再次以指數方式遞增。這次將第 8 個索引中的元素與鍵元素進行比較，但沒有找到匹配項。

但是，第 8 個索引中的元素大於鍵元素。因此，在當前元素塊上應用二分搜尋演算法。

步驟 5

當前元素塊包含索引 [4, 5, 6, 7] 中的元素。

在此元素塊上應用小規模二分搜尋，其中計算出的中間值為第 5 個元素。

步驟 6

在中間元素處未找到匹配項，並發現所需元素大於中間元素。因此，搜尋發生在塊的右半部分。

現在將中間值設定為第 6 個元素：

步驟 7

在第 6 個元素處仍然未找到元素，因此它現在搜尋中間元素的右半部分。

下一個中間值設定為第 7 個元素。

在這裡，在第 7 個索引處找到了該元素。

實現

在指數搜尋演算法的實現中，程式檢查每次以 2 的冪進行指數跳躍時的匹配項。如果找到匹配項，則返回元素的位置，否則程式返回不成功的搜尋。

一旦指數跳躍處的元素大於鍵元素，則在當前元素塊上執行二分搜尋。

在本章中，我們將研究四種不同語言中指數搜尋的實現。

#include <stdio.h>
#include <math.h>
int exponential_search(int[], int, int);
int main(){
   int i, n, key, pos;
   int arr[10] = {6, 11, 19, 24, 33, 54, 67, 81, 94, 99};
   n = 10;
   printf("Array elements are: ");
   int len = sizeof(arr) / sizeof(arr[0]);
   for(int j = 0; j<len; j++){
       printf("%d ", arr[j]);
   }
   key = 67;
   printf("\nThe element to be searched: %d", key);
   pos = exponential_search(arr, n, key);
   if(pos >= 0)
      printf("\nThe element is found at %d", pos);
   else
      printf("\nUnsuccessful Search");
}
int exponential_search(int a[], int n, int key){
   int i, m, low = 0, high = n - 1, mid;
   i = 1;
   m = pow(2,i);
   if(a[0] == key)
      return 0;
   while(a[m] <= key && m < n) {
      i++;
      m = pow(2,i);
      while (low <= high) {
         mid = (low + high) / 2;
         if(a[mid] == key)
            return mid;
         else if(a[mid] < key)
            low = mid + 1;
         else
            high = mid - 1;
      }
   }
   return -1;
}

Array elements are: 6 11 19 24 33 54 67 81 94 99 
The element to be searched: 67
The element is found at 6

#include <iostream>
#include <cmath>
using namespace std;
int exponential_search(int[], int, int);
int main(){
   int i, n, key, pos;
   int arr[10] = {6, 11, 19, 24, 33, 54, 67, 81, 94, 99};
   cout<<"Array elements are: ";
   for(auto j : arr){
      cout<<j<<" ";
   }
   n = 10;
   key = 67;
   cout<<"\nThe element to be searched: "<<key;
   pos = exponential_search(arr, n, key);
   if(pos >= 0)
      cout << "\nThe element is found at " << pos;
   else
      cout << "\nUnsuccessful Search";
}
int exponential_search(int a[], int n, int key){
   int i, m, low = 0, high = n - 1, mid;
   i = 1;
   m = pow(2,i);
   if(a[0] == key)
      return 0;
   while(a[m] <= key && m < n) {
      i++;
      m = pow(2,i);
      while (low <= high) {
         mid = (low + high) / 2;
         if(a[mid] == key)
            return mid;
         else if(a[mid] < key)
            low = mid + 1;
         else
            high = mid - 1;
      }
   }
   return -1;
}

Array elements are: 6 11 19 24 33 54 67 81 94 99 
The element to be searched: 67
The element is found at 6

import java.io.*;
import java.util.Scanner;
import java.lang.Math;
public class ExponentialSearch {
   public static void main(String args[]) {
      int i, n, key;
      int arr[] = {6, 11, 19, 24, 33, 54, 67, 81, 94, 99};
	  System.out.print("Array elements are: ");
	  for(int j = 0; j<arr.length; j++){
	     System.out.print(arr[j] + " ");
	  }
      n = 10;
      key = 67;
	  System.out.print("\nThe element to be searched: " + key);
      int pos = exponential_search(arr, n, key);
      if(pos >= 0)
         System.out.print("\nThe element is found at " + pos);
      else
         System.out.print("\nUnsuccessful Search");
   }
   static int exponential_search(int a[], int n, int key) {
      int i = 1;
      int m = (int)Math.pow(2,i);
      if(a[0] == key)
         return 0;
      while(a[m] <= key && m < n) {
         i++;
         m = (int)Math.pow(2,i);
         int low = 0;
         int high = n - 1;
         while (low <= high) {
            int mid = (low + high) / 2;
            if(a[mid] == key)
               return mid;
            else if(a[mid] < key)
               low = mid + 1;
            else
               high = mid - 1;
         }
      }
      return -1;
   }
}

Array elements are: 6 11 19 24 33 54 67 81 94 99 
The element to be searched: 67
The element is found at 6

import math
def exponential_search(a, n, key):
   i = 1
   m = int(math.pow(2, i))
   if(a[0] == key):
      return 0
   while(a[m] <= key and m < n):
      i = i + 1
      m = int(math.pow(2, i))
      low = 0
      high = n - 1
      while (low <= high):
         mid = (low + high) // 2
         if(a[mid] == key):
            return mid
         elif(a[mid] < key):
            low = mid + 1
         else:
            high = mid - 1
   return -1
   
arr = [6, 11, 19, 24, 33, 54, 67, 81, 94, 99]
n = len(arr);
print("Array elements are: ")
for i in range(len(arr)):
   print(arr[i], end = " ")
key = 67
print("\nThe element to be searched: ", key)
index = exponential_search(arr, n, key)
if(index >= 0):
   print("The element is found at index: ", (index))
else:
   print("\nUnsuccessful Search")

Array elements are: 
6 11 19 24 33 54 67 81 94 99 
The element to be searched:  67
The element is found at index:  6