指数搜索算法

指数搜索算法的目标是在输入数组的某个范围内进行搜索，它假设所需元素必须存在于该范围内，并在该特定的小范围内执行二分搜索。该算法也称为倍增搜索或手指搜索。

它类似于跳跃搜索，将排序后的输入划分为多个块并进行更小规模的搜索。但是，差异出现在计算划分块和应用的小规模搜索类型时（跳跃搜索应用线性搜索，指数搜索应用二分搜索）。

因此，此算法以 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