Tìm kiếm nhị phân¶

Tìm kiếm nhị phân là một thuật toán tìm kiếm hiệu quả dựa trên chiến lược chia để trị. Nó tận dụng tính chất được sắp xếp của dữ liệu để thu hẹp một nửa phạm vi tìm kiếm trong mỗi vòng lặp cho đến khi tìm thấy phần tử mục tiêu hoặc khoảng tìm kiếm trở nên rỗng.

Question

Cho một mảng nums có độ dài \(n\) với các phần tử được sắp xếp theo thứ tự tăng dần và không trùng lặp, hãy tìm kiếm và trả về chỉ số của phần tử target trong mảng. Nếu mảng không chứa phần tử đó, trả về \(-1\). Một ví dụ được minh họa trong hình dưới đây.

Như minh họa trong hình dưới đây, trước tiên chúng ta khởi tạo các con trỏ \(i = 0\) và \(j = n - 1\), lần lượt trỏ đến phần tử đầu tiên và cuối cùng của mảng, đại diện cho khoảng tìm kiếm \([0, n - 1]\). Lưu ý rằng dấu ngoặc vuông biểu thị một khoảng đóng, bao gồm cả chính các giá trị biên.

Tiếp theo, thực hiện hai bước sau trong một vòng lặp:

Tính chỉ số trung điểm \(m = \lfloor {(i + j) / 2} \rfloor\), trong đó \(\lfloor \: \rfloor\) biểu thị phép toán làm tròn xuống (floor).
So sánh nums[m] và target, phân chia thành ba trường hợp sau:
1. Khi nums[m] < target, điều này chỉ ra rằng target nằm trong khoảng \([m + 1, j]\), do đó thực hiện \(i = m + 1\).
2. Khi nums[m] > target, điều này chỉ ra rằng target nằm trong khoảng \([i, m - 1]\), do đó thực hiện \(j = m - 1\).
3. Khi nums[m] = target, điều này chỉ ra rằng đã tìm thấy target, do đó trả về chỉ số \(m\).

Nếu mảng không chứa phần tử mục tiêu, khoảng tìm kiếm cuối cùng sẽ thu hẹp lại thành rỗng. Trong trường hợp này, trả về \(-1\).

Đáng chú ý là vì cả \(i\) và \(j\) đều thuộc kiểu dữ liệu int, nên \(i + j\) có thể vượt quá phạm vi giá trị của kiểu int. Để tránh hiện tượng tràn số nguyên (integer overflow), chúng ta thường áp dụng công thức \(m = \lfloor {i + (j - i) / 2} \rfloor\) để tính trung điểm.

Mã nguồn được hiển thị dưới đây:

[file]{binary_search}-[class]{}-[func]{binary_search}

Độ phức tạp thời gian là \(O(\log n)\): Trong vòng lặp tìm kiếm nhị phân, khoảng tìm kiếm được thu hẹp một nửa sau mỗi vòng, vì vậy số lần lặp là \(\log_2 n\).

Độ phức tạp không gian là \(O(1)\): Các con trỏ \(i\) và \(j\) sử dụng không gian kích thước hằng số.

Phương pháp biểu diễn khoảng¶

Ngoài khoảng đóng được đề cập ở trên, một cách biểu diễn khoảng phổ biến khác là khoảng "đóng trái mở phải", được định nghĩa là \([0, n)\), nghĩa là biên trái bao gồm chính nó còn biên phải thì không. Dưới cách biểu diễn này, khoảng \([i, j)\) sẽ rỗng khi \(i = j\).

Chúng ta có thể triển khai một thuật toán tìm kiếm nhị phân có cùng chức năng dựa trên cách biểu diễn này:

[file]{binary_search}-[class]{}-[func]{binary_search_lcro}

Như minh họa trong hình dưới đây, dưới hai cách biểu diễn khoảng này, các thao tác khởi tạo, điều kiện vòng lặp và thu hẹp khoảng của thuật toán tìm kiếm nhị phân đều khác nhau.

Vì cả hai biên trái và phải trong cách biểu diễn "khoảng đóng" đều được định nghĩa là đóng, nên các thao tác thu hẹp khoảng thông qua các con trỏ \(i\) và \(j\) cũng mang tính đối xứng. Điều này giúp giảm thiểu sai sót, vì vậy phương pháp "khoảng đóng" thường được khuyến nghị.

Ưu điểm và hạn chế¶

Tìm kiếm nhị phân mang lại hiệu suất tốt ở cả khía cạnh thời gian và không gian.

Tìm kiếm nhị phân có hiệu suất thời gian cao. Khi khối lượng dữ liệu lớn, độ phức tạp thời gian logarit mang lại lợi thế vượt trội. Ví dụ, khi kích thước dữ liệu \(n = 2^{20}\), tìm kiếm tuyến tính cần \(2^{20} = 1048576\) vòng lặp, trong khi tìm kiếm nhị phân chỉ cần \(\log_2 2^{20} = 20\) vòng lặp.
Tìm kiếm nhị phân không yêu cầu thêm không gian. So với các thuật toán tìm kiếm yêu cầu thêm không gian bộ nhớ (như tìm kiếm dựa trên bảng băm), tìm kiếm nhị phân tiết kiệm không gian hơn.

Tuy nhiên, tìm kiếm nhị phân không phải lúc nào cũng phù hợp cho mọi tình huống, chủ yếu vì những lý do sau:

Tìm kiếm nhị phân chỉ áp dụng được cho dữ liệu đã được sắp xếp. Nếu dữ liệu đầu vào chưa được sắp xếp, việc sắp xếp chỉ để sử dụng tìm kiếm nhị phân sẽ phản tác dụng, vì các thuật toán sắp xếp thường có độ phức tạp thời gian là \(O(n \log n)\), cao hơn cả tìm kiếm tuyến tính và tìm kiếm nhị phân. Đối với các kịch bản chèn phần tử thường xuyên, việc duy trì mảng được sắp xếp yêu cầu chèn phần tử vào các vị trí cụ thể với độ phức tạp thời gian là \(O(n)\), điều này cũng rất tốn kém.
Tìm kiếm nhị phân chỉ áp dụng được cho mảng. Tìm kiếm nhị phân yêu cầu truy cập phần tử kiểu nhảy bước (không liên tục), và kiểu truy cập này không hiệu quả trong danh sách liên kết, khiến nó không phù hợp với danh sách liên kết hoặc các cấu trúc dữ liệu dựa trên danh sách liên kết.
Với lượng dữ liệu nhỏ, tìm kiếm tuyến tính có hiệu suất tốt hơn. Trong tìm kiếm tuyến tính, mỗi vòng lặp chỉ yêu cầu 1 phép toán so sánh; trong khi ở tìm kiếm nhị phân, nó yêu cầu 1 phép cộng, 1 phép chia, 1 đến 3 phép toán so sánh, và 1 phép cộng (hoặc trừ), tổng cộng 4 đến 6 phép toán đơn vị. Do đó, khi lượng dữ liệu \(n\) nhỏ, tìm kiếm tuyến tính trên thực tế nhanh hơn tìm kiếm nhị phân.