โปรแกรม C++ อัลกอริทึมการค้นหาแบบ Interpolation Search

การค้นหาแบบ Interpolation Search

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

ความซับซ้อนของ Interpolation Search

• Time Complexity: O(log₂(log₂ n)) สำหรับกรณีเฉลี่ย และ O(n) สำหรับกรณีแย่ที่สุด (เมื่อไอเท็มกระจายแบบเอ็กซ์โพเนนเชียล)

• Space Complexity: O(1)

Input - รายการข้อมูลที่เรียงลำดับ: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
Search key: 780
Output - Item found at location: 16

อัลกอริทึม

interpolationSearch(array, start, end, key)

Input: อาร์เรย์ที่เรียงลำดับแล้ว, ตำแหน่งเริ่มต้นและสิ้นสุด, และคีย์ค้นหา

Output: ตำแหน่งของคีย์ (ถ้าพบ), มิฉะนั้นคืนค่าตำแหน่งที่ผิด

เริ่มต้น
  while start <= end AND key >= array[start] AND key <= array[end]
    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
  คืนค่าตำแหน่งที่ไม่ถูกต้อง
สิ้นสุด

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

#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];
        fraction = dist / valRange;
        indexRange = end - start;
        estimate = start + (fraction * indexRange);
        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];
    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