Thuật Toán Tìm Kiếm Nhị Phân
I. Nguyên Lý Hoạt Động
Thuật toán tìm kiếm nhị phân là một kỹ thuật tìm kiếm hiệu quả, hoạt động dựa trên phương pháp chia đôi không gian tìm kiếm. Khi lần đầu tiếp cận với phương pháp này trong toán học, chúng ta thường sử dụng nó để giải các phương trình bằng cách liên tục chia đôi khoảng chứa nghiệm. Nguyên tắc này cũng được áp dụng hiệu quả trong việc tìm kiếm dữ liệu có cấu trúc trong máy tính. Ý tưởng cốt lõi: Có một khoảng tìm kiếm ban đầu, chúng ta sử dụng phần tử ở giữa của khoảng này để thử nghiệm, và sau mỗi lần thử, chúng ta thu hẹp khoảng tìm kiếm đi một nửa. Điều kiện tiên quyết cho việc sử dụng tìm kiếm nhị phân: dãy cần tìm kiếm phải được sắp xếp (tăng dần hoặc giảm dần, bài viết này chủ yếu tập trung vào trường hợp tăng dần).II. Phân Tích Thuật Toán
1. Định nghĩa Tìm kiếm nhị phân, còn gọi là tìm kiếm chia đôi, là một phương pháp tìm kiếm có hiệu suất cao. 2. Nguyên tắc cơ bản (a) Xác định vị trí trung tâm của khoảng tìm kiếm (b) So sánh giá trị cần tìm K với phần tử tại vị trí trung mid: - Nếu bằng nhau, tìm kiếm thành công và trả về vị trí - Nếu không, xác định khoảng tìm kiếm mới và tiếp tục (c) Điều chỉnh khoảng tìm kiếm: - Nếu giá trị tại mid lớn hơn K, thu hẹp khoảng thành [left, mid-1] - Nếu giá trị tại mid nhỏ hơn K, thu hẹp khoảng thành [mid+1, right] 3. Ưu và nhược điểm Ưu điểm: Độ phức tạp thời gian là O(log n), vượt trội hơn nhiều so với tìm kiếm tuần tự O(n). Nhược điểm: Mặc dù hiệu suất cao, nhưng yêu cầu dãy phải được sắp xếp trước. Việc sắp xếp bản thân đã là một thao tác tốn thời gian, ngay cả với các thuật toán sắp xếp hiệu quả cũng cần O(n log n) thời gian. 4. Ứng dụng phổ biến Tìm một giá trị cụ thể, tìm ranh giới trái, tìm ranh giới phải. 5. Khung mẫu
int timKiemNhiPhan(int[] arr, int mucTieu) {
int benTrai = 0, benPhai = ...;
while(...) {
int giua = benTrai + (benPhai - benTrai) / 2;
if (arr[giua] == mucTieu) {
...
} else if (arr[giua] < mucTieu) {
benTrai = ...
} else if (arr[giua] > mucTieu) {
benPhai = ...
}
}
return ...;
}
III. Triển Khai Thực Tế
Viết hàm TimKiemNhiPhan, trong mảng số nguyên a đã được sắp xếp tăng dần có size phần tử, tìm kiếm phần tử p. Nếu tìm thấy, trả về chỉ số phần tử, nếu không, trả về -1. Yêu cầu độ phức tạp O(log(n))
#include <iostream>
using namespace std;
int TimKiemNhiPhan(int arr[], int kichThuoc, int mucTieu) // độ phức tạp thời gian O(log(n))
{
int dau = 0; // điểm bắt đầu của khoảng tìm kiếm
int cuoi = kichThuoc - 1; // điểm kết thúc của khoảng tìm kiếm
while (dau <= cuoi) { // tiếp tục nếu khoảng tìm kiếm không rỗng
int giua = dau + (cuoi - dau) / 2; // lấy chỉ số của phần tử chính giữa
if (mucTieu == arr[giua])
return giua;
else if (mucTieu > arr[giua])
dau = giua + 1; // cập nhật điểm bắt đầu mới
else
cuoi = giua - 1; // cập nhật điểm kết thúc mới
}
return -1;
}
int mangMau[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int main()
{
int ketQua = TimKiemNhiPhan(mangMau, 10, 7);
cout << ketQua << endl;
}