指数搜索

  • Z时代
  • 2024-01-10
  • 分类：综合

指数搜索也称为双倍搜索或疾驰搜索。该机制用于查找搜索关键字可能出现的范围。如果 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:
在以下位置找到的物品： 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 //将 i 增加为 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); //列表的中间位置
      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; // 作为 2^0 = 1
      while(i < (end - start)){
         if(array[i] < key)
            i *= 2; //我将增加为 2 的幂
         else
            break; //当 array[i] 与关键元素交叉时
   }
   return binarySearch(array, i/2, i, key); //在较小范围内搜索项目
}
int main() {
   int n, searchKey, loc;
   cout << "输入项目数： ";
   cin >> n;
   int arr[n]; //创建一个大小为 n 的数组
   cout << "输入项目： " << endl;
   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }
   cout << "输入搜索键在列表中搜索： ";
   cin >> searchKey;
   if((loc = exponentialSearch(arr, 0, n, searchKey)) >= 0)
      cout << "在以下位置找到的物品： " << loc << endl;
   else
      cout << "在列表中找不到项目。" << endl;
}
输出结果
输入项目数： 20
输入项目：
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
输入搜索键在列表中搜索： 780
在以下位置找到的物品： 16

以上是 指数搜索 的全部内容， 来源链接： utcz.com/z/335636.html

回到顶部