Chương trình C++ so sánh Tìm kiếm nhị phân và Tìm kiếm tuần tự

Tìm kiếm nhị phân (Binary Search) và Tìm kiếm tuần tự (Sequential/Linear Search) đều được sử dụng trong lập trình máy tính để tìm một phần tử. Độ phức tạp thời gian của Tìm kiếm nhị phân là O(log n) và Tìm kiếm tuần tự là O(n).

Thuật toán

Bắt đầu
  Thuật toán cho Tìm kiếm nhị phân:
  Hàm BinarySearch() với 'arr' mảng dữ liệu và 'n' số lượng giá trị, chỉ số bắt đầu và kết thúc, đếm lần lặp và phần tử cần tìm trong danh sách đối số.
  Tăng bộ đếm lần lặp và so sánh giá trị mục với a[mid].
  Nếu mục < a[mid] chọn nửa đầu, ngược lại nửa sau để tiến hành tiếp.
  Trả về giá trị lần lặp khi tìm kiếm thành công.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

int BinarySearch(int a[], int start, int end, int item, int iter) {
    int mid;
    cout << "\nlần lặp " << iter+1;
    iter++;
    mid = start + (end - start + 1) / 2;
    if (item > a[end] || item < a[start] || mid == end) {
        cout << "\nKhông tìm thấy";
        return iter;
    } else if (item == a[mid]) {
        cout << "\n mục tìm thấy tại " << mid << " chỉ số.";
        return iter;
    } else if (item == a[start]) {
        cout << "\n mục tìm thấy tại " << start << " chỉ số.";
        return iter;
    } else if (item == a[end]) {
        cout << "\n mục tìm thấy tại " << end << " chỉ số.";
        return iter;
    } else if (item > a[mid])
        BinarySearch(a, mid, 9, item, iter);
    else
        BinarySearch(a, start, mid, item, iter);
}

int LinearSearch(int a[], int n, int item) {
    int i;
    for (i = 0; i < n; i++) {
        cout << "\nlần lặp " << i+1;
        if (a[i] == item) {
            cout << "\n mục tìm thấy tại " << i << " chỉ số.";
            return i+1;
        }
    }
    cout << "\nKhông tìm thấy";
    return i+1;
}

int main() {
    int n, i, B, L, a[10] = {2, 7, 14, 24, 26, 35, 38, 41, 49, 53};
    cout << "\nNhập phần tử cần tìm: ";
    cin >> n;
    cout << "\n\n\t\t\tTìm kiếm nhị phân :";
    B = BinarySearch(a, 0, 9, n, 0);
    cout << "\n\n\t\t\tTìm kiếm tuyến tính :";
    L = LinearSearch(a, 10, n);
    if (L > B)
        cout << "\n\nTìm kiếm nhị phân tốt hơn cho lần tìm kiếm này.";
    else if (L < B)
        cout << "\n\nTìm kiếm tuyến tính tốt hơn cho lần tìm kiếm này.";
    else
        cout << "\n\nCả hai đều hiệu quả như nhau cho lần tìm kiếm này.";
    return 0;
}

Kết quả

Nhập phần tử cần tìm: 7
Tìm kiếm nhị phân :
lần lặp 1
lần lặp 2
lần lặp 3
lần lặp 4
mục tìm thấy tại 1 chỉ số.
Tìm kiếm tuyến tính :
lần lặp 1
lần lặp 2
mục tìm thấy tại 1 chỉ số.
Tìm kiếm tuyến tính tốt hơn cho lần tìm kiếm này.
Nhập phần tử cần tìm: 53
Tìm kiếm nhị phân :
lần lặp 1
mục tìm thấy tại 9 chỉ số.
Tìm kiếm tuyến tính :
lần lặp 1
lần lặp 2
lần lặp 3
lần lặp 4
lần lặp 5
lần lặp 6
lần lặp 7
lần lặp 8
lần lặp 9
lần lặp 10
mục tìm thấy tại 9 chỉ số.
Tìm kiếm nhị phân tốt hơn cho lần tìm kiếm này.
Nhập phần tử cần tìm: 1
Tìm kiếm nhị phân :
lần lặp 1
Không tìm thấy
Tìm kiếm tuyến tính :
lần lặp 1
lần lặp 2
lần lặp 3
lần lặp 4
lần lặp 5
lần lặp 6
lần lặp 7
lần lặp 8
lần lặp 9
lần lặp 10
Không tìm thấy
Tìm kiếm nhị phân tốt hơn cho lần tìm kiếm này.