Cách Giải Tìm Kiếm Nhị Phân (Binary Search), Dể Hiểu
Tìm Kiếm Nhị Phân xuất phát từ khái niệm chia đôi không gian tìm kiếm để nhanh chóng xác định vị trí của một phần tử trong danh sách đã được sắp xếp. Ý tưởng này bắt nguồn từ các phương pháp toán học cổ điển, nơi việc giảm thiểu số lượng phép so sánh là bí quyết để tối ưu hóa hiệu suất tìm kiếm, thể hiện sự tinh tế trong tư duy logic.
Định Nghĩa
Tìm Kiếm Nhị Phân (Binary Search) là một thuật toán tìm kiếm có tính chất chia đôi liên tục. Nó hoạt động trên các mảng đã được sắp xếp theo thứ tự tăng dần (hoặc giảm dần). Thay vì tìm kiếm qua tất cả các phần tử trong mảng như tìm kiếm tuyến tính, tìm kiếm nhị phân sẽ chia mảng thành hai phần và kiểm tra phần giữa để xác định liệu giá trị cần tìm có ở bên trái hay bên phải của phần tử này.
Nếu giá trị ở giữa lớn hơn giá trị cần tìm, thuật toán sẽ tìm kiếm nửa mảng bên trái. Ngược lại, nếu giá trị ở giữa nhỏ hơn giá trị cần tìm, thuật toán sẽ tìm kiếm nửa mảng bên phải. Quá trình này sẽ tiếp tục lặp lại cho đến khi tìm được giá trị cần tìm hoặc mảng không còn phần tử nào để kiểm tra.
Điều kiện tiên quyết để sử dụng thuật toán này là mảng phải được sắp xếp. Nếu mảng chưa được sắp xếp, bạn cần phải sắp xếp nó trước khi áp dụng tìm kiếm nhị phân. Tìm Kiếm Nhị Phân là một trong những thuật toán hiệu quả nhất cho các bài toán tìm kiếm trong mảng đã sắp xếp, nhờ vào cách thức giảm phạm vi tìm kiếm liên tục.
Kết quả của thuật toán là chỉ số của phần tử cần tìm nếu nó tồn tại trong mảng, hoặc -1 nếu không tìm thấy. Thuật toán này chỉ hoạt động hiệu quả khi dữ liệu là mảng đã sắp xếp, và bạn cần phải biết rõ những gì bạn đang tìm kiếm.
Cách Giải
Thuật toán Tìm Kiếm Nhị Phân hoạt động trên nguyên tắc chia để trị. Sau đây là cách giải chi tiết:
- Kiểm tra giá trị ở vị trí giữa của mảng. Nếu giá trị này là mục tiêu cần tìm, thuật toán kết thúc và trả về chỉ số của nó.
- Nếu giá trị giữa nhỏ hơn mục tiêu, ta chỉ cần tìm kiếm trong nửa mảng bên phải, tức là các phần tử có chỉ số lớn hơn vị trí giữa.
- Nếu giá trị giữa lớn hơn mục tiêu, ta tìm kiếm trong nửa mảng bên trái, tức là các phần tử có chỉ số nhỏ hơn vị trí giữa.
- Tiếp tục bước 1 và 2 cho phần mảng đã được giảm kích thước sau mỗi lần so sánh. Lặp lại cho đến khi tìm thấy phần tử cần tìm hoặc khi vùng tìm kiếm trở nên rỗng (tức là không còn phần tử nào để kiểm tra).
Bạn thấy đó, với mỗi lần so sánh, chúng ta giảm số lượng phần tử cần tìm kiếm đi một nửa. Điều này làm cho thuật toán Tìm Kiếm Nhị Phân cực kỳ hiệu quả khi làm việc với các mảng lớn.
Để dể hình dung hơn, bạn có thể xem diễn họa của thuật toán tại đây: https://www.w3schools.com/dsa/dsa_algo_binarysearch.php
Triển Khai
Để triển khai thuật toán Tìm Kiếm Nhị Phân, chúng ta cần:
- Một mảng chứa các giá trị để tìm kiếm.
- Một giá trị mục tiêu để tìm kiếm trong mảng.
- Một vòng lặp chạy khi chỉ số bên trái nhỏ hơn hoặc bằng chỉ số bên phải.
- Một câu lệnh
ifđể so sánh giá trị ở giữa với giá trị mục tiêu, và trả về chỉ số nếu tìm thấy giá trị mục tiêu. - Một câu lệnh
ifđể kiểm tra nếu giá trị mục tiêu nhỏ hơn hoặc lớn hơn giá trị ở giữa, và cập nhật các biến “trái” hoặc “phải” để thu hẹp vùng tìm kiếm. - Sau vòng lặp, trả về -1 vì lúc này chúng ta biết giá trị mục tiêu không tồn tại trong mảng.
Mã TypeScript sẽ trông như sau:
import { expect } from 'jsr:@std/expect';
function binarySearch(nums: number[], target: number): number {
// Đặt biến chỉ mục bên trái ban đầu là 0
let leftIndex = 0;
// Đặt biến chỉ mục bên phải là độ dài mảng - 1
let rightIndex = nums.length - 1;
// Vòng lặp chạy khi chỉ mục bên trái vẫn nhỏ hơn hoặc bằng chỉ mục bên phải
while (leftIndex <= rightIndex) {
// Tính toán chỉ mục ở giữa của mảng hiện tại
const midIndex = Math.floor((leftIndex + rightIndex) / 2);
// Kiểm tra xem giá trị ở giữa có phải là giá trị cần tìm không
if (nums[midIndex] === target) {
// Nếu tìm thấy, trả về chỉ mục của giá trị đó
return midIndex;
}
if (target > nums[midIndex]) {
// Nếu giá trị cần tìm lớn hơn giá trị ở giữa, cập nhật chỉ mục bên trái để thu hẹp phạm vi tìm kiếm về phía bên phải
leftIndex = midIndex + 1;
} else {
// Nếu giá trị cần tìm nhỏ hơn giá trị ở giữa, cập nhật chỉ mục bên phải để thu hẹp phạm vi tìm kiếm về phía bên trái
rightIndex = midIndex - 1;
}
}
// Nếu không tìm thấy giá trị cần tìm trong mảng, trả về -1
return -1;
}
Deno.test('found', () => {
const input = [1, 2, 3, 5, 7, 8, 10, 12, 15, 19];
expect(binarySearch(input, 7)).toStrictEqual(4);
});
Deno.test('not found', () => {
const input = [1, 2, 3, 5, 7, 8, 10, 12, 15, 19];
expect(binarySearch(input, 4)).toStrictEqual(-1);
});
Big O
Trong trường hợp tốt nhất, độ phức tạp thời gian của thuật toán là O(1). Điều này xảy ra khi phần tử cần tìm nằm ở vị trí giữa mảng ngay từ lần kiểm tra đầu tiên.
Trong trường hợp xấu nhất, độ phức tạp thời gian của thuật toán là O(log n). Điều này xảy ra khi thuật toán phải lặp qua các lần chia đôi mảng cho đến khi chỉ còn một phần tử hoặc không tìm thấy giá trị. Mỗi lần chia đôi sẽ giảm số phần tử cần kiểm tra một nửa.
Trong trường hợp trung bình, độ phức tạp thời gian của thuật toán cũng là O(log n). Trường hợp này phản ánh sự phân bổ đồng đều của giá trị cần tìm trong mảng.
Khi viết độ phức tạp thời gian bằng ký hiệu Big O, chúng ta có thể chỉ cần viết là O(log n), nhưng O(log₂ n) nhắc nhở chúng ta rằng phạm vi tìm kiếm trong mảng bị chia đôi sau mỗi lần so sánh mới, điều này là khái niệm cơ bản của Tìm Kiếm Nhị Phân. Vì vậy, trong trường hợp này, chúng ta sẽ giữ lại chỉ số cơ sở 2.
Độ phức tạp không gian của thuật toán là O(1), vì thuật toán chỉ cần sử dụng một vài biến phụ như leftIndex, rightIndex, và midIndex để thực hiện việc tìm kiếm mà không cần thêm bộ nhớ phụ.
Toàn Cảnh
Tìm Kiếm Nhị Phân không chỉ là một công cụ tìm kiếm đơn giản mà còn là nền tảng cho các thuật toán phức tạp khác. Nó đóng vai trò quan trọng trong nhiều hệ thống, từ cơ sở dữ liệu đến công cụ tìm kiếm trên Internet.
Hãy tưởng tượng một công cụ tìm kiếm cần phải kiểm tra hàng triệu kết quả: một phương pháp tìm kiếm nhanh như Tìm Kiếm Nhị Phân sẽ giúp tiết kiệm tài nguyên và tăng tốc độ.
Hơn nữa, trong các cấu trúc dữ liệu như cây nhị phân, ý tưởng phân chia liên tục này được tận dụng triệt để, giúp tìm kiếm và sắp xếp nhanh chóng.
Trong hệ sinh thái rộng hơn, Tìm Kiếm Nhị Phân là mảnh ghép cơ bản giúp xây dựng các thuật toán phức tạp hơn, tối ưu hơn.
Ứng Dụng
Trong lập trình, Tìm Kiếm Nhị Phân thường được dùng trong các hệ thống yêu cầu tìm kiếm nhanh trên dữ liệu lớn, như ứng dụng quản lý dữ liệu và sắp xếp dữ liệu.
Ví dụ, khi bạn tìm kiếm một sản phẩm trên trang web thương mại điện tử, hệ thống có thể dùng Tìm Kiếm Nhị Phân trên danh sách đã sắp xếp của sản phẩm.
Trong khoa học máy tính, Tìm Kiếm Nhị Phân hỗ trợ trong các thuật toán về Cây và Bảng Băm, những công cụ cơ bản cho quản lý dữ liệu phức tạp.
Trong công nghệ hiện đại, từ hệ thống gợi ý của mạng xã hội đến các cơ sở dữ liệu lớn, Tìm Kiếm Nhị Phân luôn là công cụ hỗ trợ đắc lực cho việc tìm kiếm.
Hiểu Lầm
Nhiều người nhầm lẫn rằng Tìm Kiếm Nhị Phân có thể hoạt động trên bất kỳ mảng nào. Thực tế, mảng cần được “sắp xếp” trước khi áp dụng thuật toán.
Một hiểu lầm khác là Tìm Kiếm Nhị Phân sẽ luôn tìm được giá trị mục tiêu. Tuy nhiên, nếu giá trị không có trong mảng, kết quả sẽ là -1.
Người mới thường quên cập nhật đúng chỉ số trái/phải, dẫn đến lỗi trong việc xác định phạm vi tìm kiếm.
Tìm Kiếm Nhị Phân không thích hợp cho các dữ liệu không sắp xếp hoặc quá nhỏ, vì chi phí sắp xếp đôi khi còn tốn kém hơn Tìm Kiếm Tuần Tự.
Tóm Tắt
Tìm Kiếm Nhị Phân là một phương pháp tìm kiếm hiệu quả trong mảng đã sắp xếp, dựa trên việc chia đôi phạm vi tìm kiếm.
Nó giảm đáng kể thời gian tìm kiếm từ O(n) xuống O(log n), rất hữu ích trong các hệ thống cần xử lý dữ liệu lớn.
Tuy nhiên, nó yêu cầu mảng phải được sắp xếp và có một số hạn chế nhất định khi dữ liệu chưa được xử lý.
Cuối cùng, Tìm Kiếm Nhị Phân là một thuật toán cơ bản, dễ hiểu nhưng cực kỳ mạnh mẽ khi được áp dụng đúng cách.