โปรแกรม C++ เพื่อใช้งาน Interpolation Search Algorithm

สำหรับเทคนิคการค้นหาแบบไบนารี รายการจะแบ่งออกเป็นส่วนเท่าๆ กัน สำหรับเทคนิคการค้นหาการประมาณค่า กระบวนการจะพยายามค้นหาตำแหน่งที่แน่นอนโดยใช้สูตรการประมาณค่า หลังจากพบตำแหน่งโดยประมาณแล้ว ก็สามารถแยกรายการโดยใช้ตำแหน่งนั้นได้ เนื่องจากพยายามค้นหาตำแหน่งที่แน่นอนทุกครั้ง ดังนั้นเวลาในการค้นหาจึงลดลง เทคนิคนี้หาไอเทมได้ง่ายถ้าไอเทมกระจายสม่ำเสมอ

ความซับซ้อนของเทคนิคการค้นหา Interpolation

• ความซับซ้อนของเวลา:O(log₂ (log₂ n)) สำหรับกรณีเฉลี่ยและ O(n) สำหรับกรณีที่เลวร้ายที่สุด (เมื่อมีการกระจายรายการแบบทวีคูณ)

• ความซับซ้อนของอวกาศ: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

อัลกอริทึม

interpolationSearch(array, start, end, key)

ป้อนข้อมูล :อาร์เรย์ที่จัดเรียง ตำแหน่งเริ่มต้นและสิ้นสุด และปุ่มค้นหา

ผลผลิต :ตำแหน่งของกุญแจ (หากพบ) มิฉะนั้น ตำแหน่งที่ไม่ถูกต้อง

Begin
   while start <= end AND key >= array[start] AND key <= array[end] do
      dist := key – array[start]
      valRange := array[end] – array[start]
      fraction := dist / valRange
      indexRange := end – start
      estimate := start + (fraction * indexRange)
      if array[estimate] = key then
         return estimate position
      if array[estimate] < key then
         start := estimate + 1
      else
         end = estimate -1
   done
   return invalid position
End

โค้ดตัวอย่าง

#include<iostream>
using namespace std;
int interpolationSearch(int array[], int start, int end, int key) {
   int dist, valRange, indexRange, estimate;
   float fraction;
   while(start <= end && key >= array[start] && key <= array[end]) {
      dist = key - array[start];
      valRange = array[end] - array[start];     //range of value
      fraction = dist / valRange;
      indexRange = end - start;
      estimate = start + (fraction * indexRange);      //estimated position of the key
      if(array[estimate] == key)
         return estimate;
      if(array[estimate] < key)
         start = estimate +1;
      else
         end = estimate - 1;
   }
   return -1;
}
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 = interpolationSearch(arr, 0, n-1, 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