Chương trình C++ tìm kiếm dãy đã sắp xếp bằng Chia để trị với hỗ trợ số Fibonacci

Trong chương trình C++ này, chúng ta triển khai phương pháp Chia để trị (Divide and Conquer) sử dụng các số Fibonacci. Sử dụng các số Fibonacci, chúng ta tính toán chỉ số giữa (mid) của mảng dữ liệu để tìm kiếm mục dữ liệu. Độ phức tạp thời gian của phương pháp này là O(log n).

Thuật toán

Bắt đầu
  Gán dữ liệu vào mảng theo thứ tự đã sắp xếp.
  Nhập phần tử cần tìm kiếm.
  Gọi hàm FibonacciSearch().
  Tính giá trị mid bằng biểu thức 'start + fib[index-2]'.
  Nếu mục chọn bằng giá trị tại chỉ số mid, in kết quả và trả về main.
  Nếu nhỏ hơn giá trị tại mid, tiến hành với mảng con bên trái.
  Nếu lớn hơn giá trị tại mid, tiến hành với mảng con bên phải.
  Nếu mid tính được bằng start hoặc end thì mục không tìm thấy trong mảng.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

void FibonacciSearch(int *a, int start, int end, int *fib, int index, int item) {
    int mid;
    mid = start + fib[index-2];
    if (item == a[mid]) {
        cout << "\n mục tìm thấy tại " << mid << " chỉ số.";
        return;
    } else if (item == a[start]) {
        cout << "\n mục tìm thấy tại " << start << " chỉ số.";
        return;
    } else if (item == a[end]) {
        cout << "\n mục tìm thấy tại " << end << " chỉ số.";
        return;
    } else if (mid == start || mid == end) {
        cout << "\nPhần tử không tìm thấy";
        return;
    } else if (item > a[mid])
        FibonacciSearch(a, mid, end, fib, index-1, item);
    else
        FibonacciSearch(a, start, mid, fib, index-2, item);
}

int main() {
    int n, i, fib[20], a[10] = {3, 7, 55, 86, 7, 15, 26, 30, 46, 95};
    char ch;
    fib[0] = 0;
    fib[1] = 1;
    i = 1;
    while (fib[i] < 10) {
        i++;
        fib[i] = fib[i-1] + fib[i-2];
    }
    up:
    cout << "\nNhập phần tử cần tìm: ";
    cin >> n;
    FibonacciSearch(a, 0, 9, fib, i, n);
    cout << "\n\n\tBạn có muốn tìm kiếm thêm...nhập lựa chọn(y/n)?";
    cin >> ch;
    if (ch == 'y' || ch == 'Y')
        goto up;
    return 0;
}

Kết quả

Nhập phần tử cần tìm: 26
mục tìm thấy tại 6 chỉ số.
Bạn có muốn tìm kiếm thêm...nhập lựa chọn(y/n)?y
Nhập phần tử cần tìm: 45
phần tử không tìm thấy
Bạn có muốn tìm kiếm thêm...nhập lựa chọn(y/n)?n