Chương trình C++ thực hiện Tìm kiếm nhị phân đồng nhất (Uniform Binary Search)

Trong tìm kiếm nhị phân đồng nhất, chúng ta triển khai tìm kiếm nhị phân bằng cách sử dụng bảng tra cứu (lookup table). Đây là một cải tiến của tìm kiếm nhị phân vì tra cứu bảng nhanh hơn phép dịch và cộng. Độ 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.
  Tính độ dài tối đa của mảng tra cứu và khai báo mảng mới 'del'.
  Gán giá trị cho mảng tra cứu là n/2, n/4, ... cho đến '0', nơi n là độ dài mảng dữ liệu.
  Gọi hàm UniBinarySearch().
  Gán mid bằng giá trị tại chỉ số '0' của mảng 'dl' và so sánh khóa với giá trị tại chỉ số mid.
  Nếu khóa bằng nhau thì trả về giá trị chỉ số cho main.
  Nếu giá trị chỉ số trong 'dal' bằng 0 thì phần tử không có, trả về -1 cho main.
  Nếu nhỏ hơn, trừ giá trị tiếp theo lưu trong mảng 'dal' và dịch con trỏ đến giá trị tiếp theo trong 'dal'.
  Nếu lớn hơn, cộng giá trị tiếp theo lưu trong mảng 'dal' và dịch con trỏ đến giá trị tiếp theo trong 'dal'.
  In giá trị chỉ số trả về bởi hàm và hỏi lựa chọn của người dùng để tìm kiếm thêm.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

void lookUpArray(int *a, int N) {
    int power = 1, i = 0;
    do {
        int half = power;
        power *= 2;
        a[i] = (N + half) / power;
        i++;
    } while (a[i-1] != 0);
}

int UniBinarySearch(int *a, int *dal, int key) {
    int i = dal[0] - 1, d = 0;
    flag:
    if (key == a[i]) return i;
    else if (dal[d] == 0) return -1;
    else {
        if (key < a[i]) {
            i -= dal[++d];
            goto flag;
        } else {
            i += dal[++d];
            goto flag;
        }
    }
}

int main(void) {
    int i, n = 10, d = 0, pow = 1, index;
    char ch;
    int a[10] = {2, 6, 7, 10, 12, 14, 12, 16, 20, 26};
    while (pow <= n) {
        pow *= 2;
        d++;
    }
    int del[d];
    lookUpArray(del, n);
    up:
    cout << "\nNhập phần tử cần tìm: ";
    cin >> n;
    index = UniBinarySearch(a, del, n);
    if (index == -1)
        cout << "\nKhông tìm thấy mục";
    else
        cout << "\nMục " << n << " tìm thấy ở " << index+1 << " vị trí";
    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: 7
Mục 7 tìm thấy ở 3 vị trí
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: 21
Không tìm thấy mục
Bạn có muốn tìm kiếm thêm...nhập lựa chọn(y/n)?