设计与分析 - 指数搜索


指数搜索算法以输入数组的一个范围为目标,其中假定所需元素必须存在于该范围内,并在该特定的小范围上执行二分搜索。该算法也称为加倍搜索或手指搜索。

它类似于跳跃搜索,将排序后的输入分成多个块并进行更小规模的搜索。然而,在执行计算以划分块以及应用的较小规模搜索的类型(跳跃搜索应用线性搜索而指数搜索应用二分搜索)时会出现差异。

因此,该算法以 2 的幂指数跳跃。简单来说,搜索是在使用 pow(2, k) 划分的块上执行的,其中 k 是大于或等于 0 的整数。一旦位置 pow( 2、n)大于关键元素,则对当前块进行二分查找。

搜索_for_42

指数搜索算法

在指数搜索算法中,跳转从数组的第一个索引开始。因此,我们手动比较第一个元素作为算法的第一步。

步骤 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;因此,由于没有找到匹配项,因此跳转从第一个索引开始。

搜索_for_81

第2步

初始化 i = 1 后,将关键元素与第一个索引中的元素进行比较。这里,第一个索引中的元素与键元素不匹配。所以它再次以 2 的幂指数递增。

索引增加到 2 m = 2 1 = 将第二索引中的元素与关键元素进行比较。

再次增加

它仍然不匹配,因此再次递增。

步骤3

索引再次以 2 的幂递增。

2 2 = 4 = 将第 4索引中的元素与关键元素进行比较,但尚未找到匹配项。

第四个索引比较

步骤4

该指数再次呈指数增长。这次将第 8 个索引中的元素与关键元素进行比较,没有找到匹配项。

未找到匹配项

但是,第 8 个索引中的元素大于键元素。因此,二分搜索算法应用于当前元素块。

步骤5

当前元素块包括索引 [4, 5, 6, 7] 中的元素。

当前块元素

小规模二分搜索应用于该元素块,其中 mid 被计算为第 5元素。

计算的第 5 个元素

步骤6

在中间元素处未找到匹配项,并且表明所需元素大于中间元素。因此,搜索发生在块的右半部分。

现在中点被设置为第 6元素 -

第 6 个元素

步骤7

在第 6个元素处仍未找到该元素,因此它现在在中间元素的右半部分中搜索。

下一个 mid 被设置为第 7元素。

元素_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; key = 67; 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; }

输出

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}; n = 10; key = 67; 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; }

输出

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}; n = 10; key = 67; 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; } }

输出

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); key = 67 index = exponential_search(arr, n, key) if(index >= 0): print("The element is found at index: ", (index)) else: print("Unsuccessful Search")

输出

The element is found at index:  6