Tìm kiếm theo cấp số nhân còn được gọi là tìm kiếm nhân đôi hoặc phi mã. Cơ chế này được sử dụng để tìm phạm vi mà khóa tìm kiếm có thể xuất hiện. Nếu L và U là cận trên và cận dưới của danh sách, thì L và U đều là lũy thừa của 2. Đối với phần cuối cùng, U là vị trí cuối cùng của danh sách. Vì lý do đó, nó được gọi là cấp số nhân.
Sau khi tìm thấy phạm vi cụ thể, nó sử dụng kỹ thuật tìm kiếm nhị phân để tìm vị trí chính xác của khóa tìm kiếm.
Sự phức tạp của Kỹ thuật tìm kiếm theo cấp số nhân
- Độ phức tạp về thời gian: O (1) cho trường hợp tốt nhất. O (log2 i) cho trường hợp trung bình hoặc xấu nhất. Vị trí của tôi là vị trí có khóa tìm kiếm.
- Mức độ phức tạp của không gian: O (1)
Đầu vào và Đầu ra
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
Thuật toán
Tìm kiếm nhị phân (mảng, bắt đầu, kết thúc, khóa)
Đầu vào : Một mảng được sắp xếp, vị trí bắt đầu và kết thúc, và phím tìm kiếm
Đầu ra - vị trí của chìa khóa (nếu được tìm thấy), nếu không thì sai vị trí.
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
Tìm kiếm theo cấp số nhân (mảng, bắt đầu, kết thúc, khóa)
Đầu vào: Một mảng được sắp xếp, vị trí bắt đầu và kết thúc, và phím tìm kiếm
Đầu ra: vị trí của chìa khóa (nếu được tìm thấy), nếu không thì sai vị trí.
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
Ví dụ
#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;
} Đầu ra
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