指数搜索算法
指数搜索算法针对输入数组的某个范围，假设所需元素一定存在于该范围内，并对该特定的小范围执行二分查找。该算法也称为加倍搜索或手指搜索。
它与跳跃搜索类似，将已排序的输入分成多个块，并进行较小规模的搜索。然而，差异出现在执行块划分计算和应用的小规模搜索类型上（跳跃搜索采用线性搜索，指数搜索采用二分搜索）。
因此，该算法以 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；因此，由于未找到匹配项，跳转从第一个索引开始。
步骤 2
初始化 i = 1 后，将关键元素与第一个索引中的元素进行比较。此处，第一个索引中的元素与关键元素不匹配。因此，它再次以 2 的幂次方递增。
索引递增至 2m = 21 = 将第 2 个索引中的元素与关键元素进行比较。
仍然不匹配，因此再次递增。
步骤 3
索引再次以 2 的幂次方递增。
22 = 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("
The element to be searched: %d", key);
pos = exponential_search(arr, n, key);
if(pos >= 0)
printf("
The element is found at %d", pos);
else
printf("
Unsuccessful 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<<"
The element to be searched: "<<key;
pos = exponential_search(arr, n, key);
if(pos >= 0)
cout << "
The element is found at " << pos;
else
cout << "
Unsuccessful 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("
The element to be searched: " + key);
int pos = exponential_search(arr, n, key);
if(pos >= 0)
System.out.print("
The element is found at " + pos);
else
System.out.print("
Unsuccessful 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("
The element to be searched: ", key)
index = exponential_search(arr, n, key)
if(index >= 0):
print("The element is found at index: ", (index))
else:
print("
Unsuccessful 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
