資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究指數搜尋
指數搜尋也稱為雙倍或加倍搜尋。此機制用於查詢可能出現搜尋鍵的範圍。如果 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: Item found at location: 16
演算法
binarySearch(陣列，開始位置，結束位置，鍵)
輸入：一個已排序的陣列，開始位置和結束位置以及搜尋鍵
輸出：鍵的位置（如果找到），否則位置錯誤。
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(陣列，開始位置，結束位置，鍵)
輸入：一個已排序的陣列，開始位置和結束位置以及搜尋鍵
輸出：找到鍵的位置（如果找到），否則為錯誤位置。
Begin if (end – start) <= 0 then return invalid location i := 1 while i < (end - start) do if array[i] < key then i := i * 2 //increase i as power of 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); //mid location of the list
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; // as 2^0 = 1
while(i < (end - start)){
if(array[i] < key)
i *= 2; //i will increase as power of 2
else
break; //when array[i] corsses the key element
}
return binarySearch(array, i/2, i, key); //search item in the smaller range
}
int main() {
int n, searchKey, loc;
cout << "Enter number of items: ";
cin >> n;
int arr[n]; //create an array of size n
cout << "Enter items: " << endl;
for(int i = 0; i< n; i++) {
cin >> arr[i];
}
cout << "Enter search key to search in the list: ";
cin >> searchKey;
if((loc = exponentialSearch(arr, 0, n, searchKey)) >= 0)
cout << "Item found at location: " << loc << endl;
else
cout << "Item is not found in the list." << endl;
}輸出
Enter number of items: 20 Enter items: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 Enter search key to search in the list: 780 Item found at location: 16
更新於：2020 年 6 月 15 日
4K+ 次觀看
廣告