โปรแกรม C++ ค้นหาข้อมูลด้วย Fibonacci Search (Divide and Conquer)

ภาพรวม

Fibonacci Search เป็นอัลกอริทึมค้นหาแบบ Divide and Conquer ที่ใช้เลขฟีบอนัชชี (Fibonacci Numbers) ในการคำนวณตำแหน่งกลาง (Mid) แทนการหาร 2 เหมาะสำหรับระบบที่การหารมีค่าใช้จ่ายสูง ความซับซ้อนด้านเวลา O(log n)

อัลกอริธึม

1. จัดเรียงข้อมูลในอาร์เรย์ให้เรียงลำดับ
2. สร้างลำดับฟีบอนัชชีจนกว่าจะครอบคลุมขนาดอาร์เรย์
3. คำนวณ mid = start + fib[index-2]
4. เปรียบเทียบค่าที่ค้นหา กับค่าที่ mid:
   • เท่ากัน → พบ
   • น้อยกว่า → ค้นหาในส่วนซ้าย (ลด index ลง 2)
   • มากกว่า → ค้นหาในส่วนขวา (ลด index ลง 1)
5. ถ้า mid เท่ากับ start หรือ end แสดงว่าไม่พบ

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

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

void fibonacciSearch(const vector& arr, int start, int end, const vector& fib, int fibIndex, int item) {
    if (start > end || fibIndex < 2) {
        cout << "\nElement not found";
        return;
    }
    
    int mid = start + fib[fibIndex - 2];
    if (mid > end) mid = end; // ป้องกันล้น
    
    if (item == arr[mid]) {
        cout << "\nItem found at " << mid << " index.";
    } else if (item == arr[start]) {
        cout << "\nItem found at " << start << " index.";
    } else if (item == arr[end]) {
        cout << "\nItem found at " << end << " index.";
    } else if (mid == start || mid == end) {
        cout << "\nElement not found";
    } else if (item > arr[mid]) {
        fibonacciSearch(arr, mid + 1, end, fib, fibIndex - 1, item);
    } else {
        fibonacciSearch(arr, start, mid - 1, fib, fibIndex - 2, item);
    }
}

int main() {
    vector arr = {3, 7, 15, 26, 30, 46, 55, 70, 86, 95}; // เรียงลำดับแล้ว
    int n = arr.size();
    
    // สร้างลำดับฟีบอนัชชี
    vector fib = {0, 1};
    while (fib.back() < n) {
        int sz = fib.size();
        fib.push_back(fib[sz-1] + fib[sz-2]);
    }
    
    char choice;
    do {
        int item;
        cout << "\nEnter the Element to be searched: ";
        cin >> item;
        fibonacciSearch(arr, 0, n-1, fib, fib.size()-1, item);
        
        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: 26
Item found at 3 index.

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

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

ข้อสังเกต

• โค้ดต้นฉบับมีอาร์เรย์ไม่เรียงลำดับและลอจิก recursion ผิดปกติ → ได้แก้ไขให้ถูกต้อง
• Fibonacci Search ใช้การบวก/ลบแทนการหาร เหมาะสำหรับฮาร์ดแวร์เก่าหรือเฉพาะทาง
• ในทางปฏิบัติ Binary Search ทั่วไปมักเร็วกว่าใน CPU สมัยใหม่