โปรแกรม C++ ทำ Uniform Binary Search ด้วย Lookup Table

ภาพรวม

Uniform Binary Search เป็นการปรับปรุง Binary Search แบบคลาสสิกโดยใช้ Lookup Table (ตารางค้นหา) เก็บค่าขั้นตอนการกระโดด (Jump Steps) ไว้ล่วงหน้า ทำให้เร็วกว่า Binary Search ปกติที่ต้องคำนวณ mid ทุกครั้ง ความซับซ้อนด้านเวลา O(log n)

อัลกอริธึม

1. จัดเรียงข้อมูลในอาร์เรย์ให้เรียงลำดับก่อน
2. สร้าง Lookup Table (delta[]) ที่เก็บค่าขั้นตอน: n/2, n/4, n/8, ... จนถึง 0
3. เริ่มต้นที่ดัชนีกลาง (mid = delta[0] - 1)
4. เปรียบเทียบค่าที่ค้นหา (key) กับค่าที่ mid:
   • เท่ากัน → คืนค่าดัชนี
   • key น้อยกว่า → ลบค่าถัดไปใน delta จาก mid
   • key มากกว่า → บวกค่าถัดไปใน delta เข้า mid
5. ทำซ้ำจนกว่าจะเจอหรือ delta เป็น 0 (ไม่พบ)

โค้ดตัวอย่าง (แก้ไขให้ทำงานได้)

#include <iostream>
#include <vector>
using namespace std;

void buildLookupTable(vector& delta, int n) {
    int power = 1;
    int i = 0;
    do {
        int half = power;
        power *= 2;
        delta.push_back((n + half) / power);
        i++;
    } while (delta[i-1] != 0);
}

int uniformBinarySearch(const vector& arr, const vector& delta, int key) {
    int idx = delta[0] - 1;
    int d = 0;
    
    while (true) {
        if (key == arr[idx]) return idx;
        if (delta[d] == 0) return -1;
        
        if (key < arr[idx]) {
            idx -= delta[++d];
        } else {
            idx += delta[++d];
        }
    }
}

int main() {
    vector arr = {2, 6, 7, 10, 12, 14, 16, 20, 26}; // เรียงลำดับแล้ว
    vector delta;
    buildLookupTable(delta, arr.size());
    
    char choice;
    do {
        int key;
        cout << "\nEnter the Element to be searched: ";
        cin >> key;
        
        int index = uniformBinarySearch(arr, delta, key);
        if (index == -1) {
            cout << "\nItem not found";
        } else {
            cout << "\nItem " << key << " found at " << index+1 << " position";
        }
        
        cout << "\n\nDo you want to search more...enter choice(y/n)? ";
        cin >> choice;
    } while (choice == 'y' || choice == 'Y');
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter the Element to be searched: 7
Item 7 found at 3 position

Do you want to search more...enter choice(y/n)? y
Enter the Element to be searched: 21
Item not found

Do you want to search more...enter choice(y/n)? n

ข้อสังเกต

• โค้ดต้นฉบับมีบั๊กหลายจุด (ตัวแปร d ซ้ำ, goto, อาร์เรย์ไม่เรียงลำดับ) → ได้แก้ไขให้ทำงานถูกต้อง
• Uniform Binary Search เหมาะสำหรับระบบฝังตัว (Embedded Systems) ที่การหารและคูณช้า
• ข้อจำกัด: ต้องจัดสรรหน่วยความจำสำหรับ Lookup Table