Trong chương trình này, chúng ta cần triển khai tìm kiếm nhị phân để tìm sự tồn tại của một chuỗi tìm kiếm trong một mảng. Độ phức tạp thời gian của tìm kiếm nhị phân là O(log n).
Các bước yêu cầu và mã giả
Bắt đầu Hàm BinarySearch() có '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à b[0] là 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ị chỉ số cho main. Trong main(), so sánh tuần tự các mục còn lại của chuỗi tìm kiếm với các mục tiếp theo trong mảng. In phạm vi chỉ số của chuỗi tìm thấy. 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;
iter++;
mid = start + (end - start + 1) / 2;
if (item > a[end] || item < a[start] || mid == end) {
cout << "\nKhông tìm thấy";
return -1;
} else if (item == a[mid]) {
return mid;
} else if (item == a[start]) {
return start;
} else if (item == a[end]) {
return end;
} else if (item > a[mid])
BinarySearch(a, mid, end, item, iter);
else
BinarySearch(a, start, mid, item, iter);
}
int main() {
int n, i, flag = 0, Bin, len = 9, a[10] = {1, 7, 15, 26, 29, 35, 38, 40, 49, 51};
cout << "\nNhập số phần tử trong chuỗi tìm kiếm: ";
cin >> n;
int b[n];
for (i = 0; i < n; i++) {
cin >> b[i];
}
Bin = BinarySearch(a, 0, len, b[0], 0);
if (Bin == -1) {
cout << "\nKhông tìm thấy.";
return 0;
} else {
for (i = Bin; i < n + Bin; i++)
if (a[i] != b[i - Bin])
flag = 4;
if (flag == 4)
cout << "\nKhông tìm thấy.";
else
cout << "\nChuỗi tìm thấy giữa chỉ số " << Bin << " và " << Bin + n << ".";
}
return 0;
}
Kết quả
Nhập số phần tử trong chuỗi tìm kiếm: 4 15 26 29 35 Chuỗi tìm thấy giữa chỉ số 2 và 6.