NỘI DUNG
Giới thiệu thuật toán tìm kiếm nhị phân
Thuật toán tìm kiếm nhị phân (Binary search algorithm) là một thuật toán tìm kiếm phổ biến trong lập trình, được sử dụng để tìm kiếm một phần tử trong một mảng đã được sắp xếp. Thuật toán tìm kiếm nhị phân sử dụng phương pháp chia để trị và hoạt động nhanh hơn so với các phương pháp tìm kiếm khác như tìm kiếm tuần tự.
Thuật toán tìm kiếm nhị phân hoạt động bằng cách chia mảng thành hai nửa và so sánh phần tử tại giữa mảng với giá trị cần tìm kiếm. Nếu phần tử tại giữa bằng với giá trị cần tìm kiếm, thuật toán kết thúc. Nếu phần tử tại giữa lớn hơn giá trị cần tìm kiếm, thuật toán tiếp tục tìm kiếm trong nửa đầu tiên của mảng, ngược lại, nếu phần tử tại giữa nhỏ hơn giá trị cần tìm kiếm, thuật toán tiếp tục tìm kiếm trong nửa thứ hai của mảng.
Lịch sử thuật toán tìm kiếm nhị phân
Thuật toán tìm kiếm nhị phân được coi là một trong những thuật toán cổ điển nhất trong khoa học máy tính. Ý tưởng của thuật toán này đã được sử dụng từ thời kỳ cổ đại.
Tìm kiếm nhị phân được ghi nhận lần đầu tiên vào thế kỷ thứ 1 sau Công nguyên bởi nhà toán học người Hy Lạp Euclid trong cuốn Elements của ông. Euclid đã sử dụng phương pháp chia để trị để giải quyết các vấn đề liên quan đến hình học, nhưng ông cũng đã áp dụng phương pháp này để giải quyết vấn đề tìm kiếm.
Trong thế kỷ 19, nhà toán học người Đức Julius Wilhelm Zacharias Weber và Carl Friedrich Gauss đều đã sử dụng thuật toán tìm kiếm nhị phân trong các nghiên cứu của họ. Thuật toán này đã được sử dụng rộng rãi trong các ứng dụng thực tế, như tìm kiếm từ khóa trên Internet, trong các hệ thống cơ sở dữ liệu, và trong các ứng dụng khoa học và kỹ thuật khác.
Tuy nhiên, việc tìm kiếm nhị phân không phải lúc nào cũng hiệu quả nhất, đặc biệt là khi phải xử lý các dữ liệu không đồng nhất. Do đó, các nhà nghiên cứu đã phát triển các thuật toán tìm kiếm khác như tìm kiếm tuần tự, tìm kiếm nhiều khóa hơn, tìm kiếm tuyến tính và tìm kiếm nhảy dấu. Tuy nhiên, tìm kiếm nhị phân vẫn là một trong những thuật toán quan trọng nhất trong khoa học máy tính và được sử dụng rộng rãi trong các ứng dụng thực tế.
Các bước thực hiện thuật toán tìm kiếm nhị phân
Thuật toán tìm kiếm nhị phân là một thuật toán đơn giản, hiệu quả để tìm kiếm một phần tử trong một mảng đã được sắp xếp. Các bước thực hiện thuật toán như sau:
Bước 1. Xác định phần tử trung tâm của mảng.
Bước 2. So sánh phần tử trung tâm với phần tử cần tìm kiếm. Nếu bằng nhau, trả về vị trí của phần tử đó trong mảng.
Bước 3. Nếu phần tử cần tìm kiếm nhỏ hơn phần tử trung tâm, ta thực hiện thuật toán tìm kiếm nhị phân trên một mảng con bên trái của phần tử trung tâm.
Bước 4. Nếu phần tử cần tìm kiếm lớn hơn phần tử trung tâm, ta thực hiện thuật toán tìm kiếm nhị phân trên một mảng con bên phải của phần tử trung tâm.
Bước 5. Lặp lại quá trình trên cho mảng con tương ứng cho đến khi tìm thấy phần tử cần tìm kiếm hoặc không còn phần tử nào để tìm kiếm.
Bước 6. Nếu không tìm thấy phần tử cần tìm kiếm sau khi thực hiện thuật toán trên toàn bộ mảng, trả về giá trị không tồn tại hoặc -1.
Để thực hiện được thuật toán tìm kiếm nhị phân, mảng cần được sắp xếp trước. Thuật toán tìm kiếm nhị phân là một trong những thuật toán đơn giản và hiệu quả nhất để tìm kiếm phần tử trong mảng đã sắp xếp.
Ví dụ về thuật toán nhị phân
Giả sử ta có một mảng đã sắp xếp là:
[2, 5, 7, 11, 13, 15, 18, 21, 25, 28]Ta muốn tìm kiếm phần tử có giá trị là 13.
Bước 1: Ta xác định phần tử trung tâm của mảng. Trong trường hợp này, phần tử trung tâm là 15 (phần tử ở giữa của mảng).
Bước 2: So sánh phần tử trung tâm (15) với phần tử cần tìm kiếm (13). Phần tử trung tâm lớn hơn phần tử cần tìm kiếm, do đó, ta sẽ tìm kiếm trên mảng con bên trái của phần tử trung tâm.
Bước 3: Ta thực hiện lại bước 1 và 2 trên mảng con bên trái của phần tử trung tâm [2, 5, 7, 11, 13]. Phần tử trung tâm là 7, và phần tử cần tìm kiếm là lớn hơn phần tử trung tâm. Do đó, ta sẽ tìm kiếm trên mảng con bên phải của phần tử trung tâm.
Bước 4: Ta thực hiện lại bước 1 và 2 trên mảng con bên phải của phần tử trung tâm [11, 13]. Phần tử trung tâm là 13, và phần tử cần tìm kiếm bằng phần tử trung tâm. Do đó, ta đã tìm thấy phần tử cần tìm kiếm.
Bước 5: Trả về vị trí của phần tử cần tìm kiếm trong mảng ban đầu. Trong trường hợp này, phần tử có giá trị là 13 nằm ở vị trí thứ 4 trong mảng ban đầu.
Kết quả: Thuật toán tìm kiếm nhị phân đã tìm thấy phần tử cần tìm kiếm và trả về vị trí của nó trong mảng ban đầu là 3 (chỉ số bắt đầu từ 0).
Cài đặt thuật toán tìm kiếm nhị phân với Python
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target = 12
result = binary_search(arr, target)
if result != -1:
print(f"Phần tử {target} được tìm thấy tại vị trí {result}")
else:
print("Phần tử không tồn tại trong mảng")
Trong ví dụ này, ta có một mảng arr chứa các số nguyên đã sắp xếp theo thứ tự tăng dần. Ta cần tìm kiếm phần tử target trong mảng này. Ta gọi hàm binary_search và truyền vào arr và target làm tham số. Nếu target được tìm thấy trong arr, hàm sẽ trả về chỉ số của phần tử đó, và chương trình sẽ in ra thông báo về vị trí của phần tử đó trong mảng. Nếu không tìm thấy, hàm sẽ trả về giá trị -1, và chương trình sẽ in ra thông báo cho biết phần tử không tồn tại trong mảng.
Cài đặt thuật toán tìm kiếm nhị phân với C++
#include <iostream>
using namespace std;
int binary_search(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 12;
int result = binary_search(arr, 0, n - 1, target);
if (result != -1) {
cout << "Phan tu " << target << " duoc tim thay tai vi tri " << result << endl;
} else {
cout << "Phan tu " << target << " khong ton tai trong mang" << endl;
}
return 0;
}
Sự khác biệt giữa tìm kiếm tuyến tính và tìm kiếm nhị phân
Tìm kiếm tuyến tính
Điều kiện để sử dụng thuật toán: mảng không được sắp xếp hoặc sắp xếp không tối ưu.
Cách thực hiện: duyệt qua từng phần tử trong mảng cho đến khi tìm thấy phần tử cần tìm hoặc hết mảng.
Độ phức tạp thời gian trung bình: O(n) với n là số phần tử trong mảng.
Tìm kiếm nhị phân
Điều kiện để sử dụng thuật toán: mảng phải được sắp xếp theo thứ tự tăng dần hoặc giảm dần.
Cách thực hiện: so sánh phần tử ở giữa mảng với phần tử cần tìm, nếu bằng nhau thì trả về vị trí đó, nếu nhỏ hơn thì tiếp tục tìm ở nửa bên trái, nếu lớn hơn thì tìm ở nửa bên phải. Lặp lại quá trình cho đến khi tìm thấy hoặc hết mảng.
Độ phức tạp thời gian trung bình: O(log n) với n là số phần tử trong mảng.
Tóm lại, hai thuật toán này đều là những phương pháp tìm kiếm trong mảng, tuy nhiên cách thực hiện và điều kiện để sử dụng khác nhau. Tìm kiếm tuyến tính thường được sử dụng khi mảng không được sắp xếp, trong khi tìm kiếm nhị phân được sử dụng khi mảng đã được sắp xếp. Tất nhiên trong quá trình thực hiện các bài toán thì thuật toán tìm kiếm nhị phân tối ưu hơn nhiều so với thuật toán tìm kiếm tuyến tính, đặc biệt là với những dãy số có số lượng phần tử lớn./.
