Nguồn: Topcoder
Người dịch:
- Nguyễn Nhật Minh Khôi - VNU University of Science. Biên soạn lại từ bản dịch của Vũ Thị Thiên Anh
Reviewer: Hoàng Xuân Nhật, Trần Quang Lộc
Tìm kiếm nhị phân [hay còn gọi là chặt nhị phân] là một trong số các thuật toán cơ bản của khoa học máy tính. Trong bài viết này, chúng ta sẽ xây dựng một nền tảng lý thuyết, sau đó đưa ra cách cài đặt thuật toán này một cách chuẩn xác.
Bài toán mở đầu: Tìm giá trị cho trước trong một dãy đã sắp xếp
Mở đầu, ta sẽ đến với bài toán sử dụng tìm kiếm nhị phân đơn giản nhất. Đề bài như sau:
Cho trước một dãy $A$ được sắp tăng dần, trả về vị trí của phần tử có giá trị $x$ trong $A$. Lưu ý: để đơn giản, ta giả sử các phần tử trong mảng $A$ có giá trị phân biệt.
Ví dụ
Đầu tiên, ta sẽ xét một ví dụ để thấy được tư tưởng của thuật toán. Cho $A = [0, 5, 13, 19, 2, 41, 55, 68, 72, 81, 98]$ và $x = 55$, thuật toán sẽ diễn ra như hình dưới:
Ở lượt tìm đầu tiên, không gian tìm kiếm là tập hợp $S = {1,\ldots,11}$ gồm tất cả các chỉ số của mảng. Bắt đầu với việc chọn phần tử trung vị của không gian tìm kiếm hiện tại [chính là $6$], ta nhận xét $A[6]=41 < 55 = x$. Do theo đề bài mảng $A$ được sắp xếp tăng dần, ta biết được tất cả các phần tử có chỉ số $1,\ldots,6$ đều nhỏ hơn giá trị cần tìm $x$. Do đó, chúng chắc chắn không thể là kết quả, khi đó không gian tìm kiếm có thể thu hẹp lại $S = {7,\ldots,11}$, tức giảm đi một nửa.
Tương tự, ở lượt tìm thứ hai, ta xét phần tử trung vị của không gian tìm kiếm hiện tại [chính là $9$], nhận thấy $A[9]=72 > 55 = x$. Cũng do mảng $A$ được sắp xếp tăng dần, ta biết được tất cả các phần tử có vị trí từ $9,\ldots,11$ đều lớn hơn giá trị cần tìm $x$. Do đó, chúng chắc chắn không thể là kết quả, khi đó không gian tìm kiếm sẽ lại giảm đi một nửa $S = {7,\ldots,8}$.
Ở lượt tìm cuối cùng, ta cũng xét phần tử trung vị của không gian tìm kiếm hiện tại ở vị trí $7$ [ở đây số lượng phần tử của không gian tìm kiếm là chẵn, do đó có hai phần tử trung vị, ta có thể chọn một trong hai đều được, ở ví dụ này ta chọn phần tử trung vị đầu tiên], Nhận thấy $A[7] = 55 = x$, ta kết luận $5$ chính là vị trí của phần tử cần tìm và dừng thuật toán.
Tổng quát hóa bài toán
Từ ví dụ trên, ta có thể dễ dàng hiểu được ý tưởng của thuật toán tìm kiếm nhị phân. Đúng như tên gọi, thuật toán sẽ liên tục chia không gian tìm kiếm thành hai nửa và loại một nửa đi. Thuật toán có thể trình bày như sau:
- Ta duy trì một không gian tìm kiếm $S$ là một dãy con các giá trị có thể là kết quả [ở đây là chỉ số các phần tử trong $A$]. Ban đầu, không gian tìm kiếm là toàn bộ các chỉ số của mảng $S={1,\ldots,n}$ với $n$ là chỉ số phần tử cuối cùng của $A$.
- Ở mỗi bước, thuật toán so sánh giá trị cần tìm với phần tử có chỉ số là trung vị trong không gian tìm kiếm. Dựa trên sự so sánh đó, cộng thêm việc ta biết dãy $A$ có thứ tự, ta có thể loại một nửa số phần tử của $S$. Lặp đi lặp lại quá trình này, cuối cùng ta sẽ được một không gian tìm kiếm bao gồm một phần tử duy nhất.
- Khi đó, nếu phần tử duy nhất đó bằng với giá trị cần tìm $x$ thì đó là nghiệm của bài toán, nếu không thì bài toán vô nghiệm.
Ở đây có hai lưu ý khi cài đặt thuật toán:
- Do không gian tìm kiếm luôn là một đoạn liên tục các giá trị nguyên, ta không cần lưu tất cả phần tử của không gian khi tìm kiếm mà chỉ cần duy trì hai biến low và high tượng trưng cho phần tử đầu và cuối của đoạn.
- Ta có thể tối ưu thuật toán hơn bằng việc dừng sớm nếu trong quá trình so sánh gặp một phần tử trung vị thỏa yêu cầu đề bài chứ không cần đợi đến khi không gian tìm kiếm chỉ còn một phần tử.
Dưới đây là code minh họa viết bằng ngôn ngữ C++. Trong trường hợp giá trị cần tìm không tồn tại trong khoảng tìm kiếm thì thuật toán sẽ trả về $-1$
int binary_search[int A[], int sizeA, int target] { int lo = 1, hi = sizeA; while [lo x$ đều hợp lệ. Tính chất này giúp chúng ta loại đi nửa sau của không gian tìm kiếm do đã biết chắc $x$ là phần tử nhỏ nhất trong nửa sau hợp lệ, ta ghi nhận $x$ là kết quả tạm thời và tiếp tục tìm xem có phần tử nào ở nửa đầu [nhỏ hơn $x$] hợp lệ hay không.Nếu ta tính giá trị $P[x]$ cho từng phần tử trong $S$ ban đầu, ta sẽ được một dãy liên tiếp các giá trị $\texttt{false}$ liền kề một dãy liên tiếp các giá trị $\texttt{true}$ [từ nay gọi là dãy $P[S]$]. Dễ thấy ta có thể áp dụng tìm kiếm nhị phân trên dãy $P[S]$ mới này để tìm giá trị $x$ nhỏ nhất thỏa mãn $P[x] = \texttt{true}$ [hoặc cũng có thể làm cách tìm giá trị $x$ lớn nhất mà $P[x] = \texttt{false}$, tuy nhiên ở đây ta không chọn cách này].
Với ví dụ đầu bài, như đã nói $P[x] = boolean[A[x] \geq 55]$. Dễ thấy $P$ thỏa mãn tính chất đầu tiên, do $A$ được sắp tăng dần nên nếu $A[x] \geq 55$ thì chắc chắn các phần tử $y$ sau $x$ đều thỏa $A[y] \geq A[x] \geq 55$. Tương tự ta cũng suy ra được, nếu $A[x] < 55$ thì chắc chắn các phần tử $y$ trước $x$ đều thỏa $A[y] \leq A[x] < 55$. Áp dụng hàm $P[x] = boolean[A[x] \geq 55]$ cho từng phần tử của $S={1,\ldots,11}$ ta có hình sau
Chú ý rằng ta thấy có thể dễ dàng xây dựng định lý chính dựa trên một hàm kiểm tra $P$ ngược lại, tức $P[S]$ sẽ là một dãy $\texttt{true}$ liên tiếp theo sau bởi $\texttt{false}$ liên tiếp. Tuy nhiên, ở đây ta sẽ chỉ xét một trường hợp để bài viết ngắn gọn hơn, trường hợp còn lại có thể làm tương tự.
Từ định lý trên, ta rút ra được mấu chốt để giải một bài toán dùng tìm kiếm nhị phân là ta cần thiết kế được hàm $P$ hợp lý sao cho thỏa mãn điều kiện trong định lý chính.
Cuối cùng, tại sao ta phải tốn công tổng quát hóa thuật toán này thay vì dùng cách làm đơn giản ở ví dụ đầu? Đó là vì nhiều bài toán không thể ở dưới dạng tìm kiếm một giá trị cụ thể, nhưng ta lại có thể định nghĩa một hàm kiểm tra thỏa yêu cầu định lý chính để có thể áp dụng tìm kiếm nhị phân. Bằng cách đó, ta có thể mở rộng lớp bài toán có thể giải bằng tìm kiếm nhị phân.
Ví dụ điển hình cho việc áp dụng định lý là với bài toán Tìm căn bậc hai, thay vì hỏi "Số $x$ nào bình phương lên thì bằng $a$?" và tìm kiếm tuần tự tất cả các trường hợp, ta có thể định nghĩa hàm $P[x]$ trả lời cho câu hỏi "$x^2$ có lớn hơn hoặc bằng $a$ hay không?" sau đó dùng tìm kiếm nhị phân để tìm $x$ nhỏ nhất thỏa mãn. Với cách làm này ta có thể đơn giản hóa bài toán thành một bài toán yes/no, hơn thế còn giảm độ phức tạp của bài toán từ $O[n]$ xuống chỉ còn $O[\log[n]]$.
Cài đặt thuật toán tổng quát
Trước khi cài đặt thuật toán, ta phải trả lời những câu hỏi sau:
- Dãy $P[S]$ của bạn có dạng $\texttt{false}-\texttt{true}$ [$\texttt{false}$ liên tiếp rồi $\texttt{true}$ liên tiếp] hay $\texttt{true}-\texttt{false}$ [ngược lại]? Ở cài đặt phía dưới sẽ mặc định dãy $P[S]$ có dạng $\texttt{false}-\texttt{true}$, vì vậy nếu dãy $P[S]$ của bạn có dạng $\texttt{true}-\texttt{false}$, hãy đảo hàm $P[x]$ của bạn ngược lại.
- Bài của bạn có luôn có nghiệm không? Nếu không hãy kiểm tra trước khi tìm kiếm nhị phân để tiết kiệm chi phí tính toán.
- Mục tiêu của bạn là tìm phần tử $\texttt{false}$ lớn nhất hay tìm phần tử $\texttt{true}$ nhỏ nhất? Ở đây sẽ trình bày cả hai cách.
- Nếu bài toán có nghiệm, hãy đảm bảo giá trị chặn dưới và chặn trên của khoảng tìm kiếm [biến lo và hi] là bắt đầu và kết thúc của một khoảng đóng mà chắc chắn chứa kết quả cần tìm [phần tử $x$ đầu tiên mà $P[x] = \texttt{true}$]. Hãy đảm bảo điều kiện này trong lúc thu hẹp không gian tìm kiếm để tránh xảy ra lỗi.
- Phạm vi tìm kiếm đã đủ rộng chưa? Sẽ có nhiều lúc chấm xong bạn nhận ra là mình thiếu vài trường hợp biên. Vì thời gian chạy chỉ tăng theo hàm logarit $O[\log[N]]$, bạn hoàn toàn có thể nâng rộng khoảng tìm kiếm ra mà ít khi lo bị quá thời gian. Tuy nhiên, phải để ý các lỗi như tràn mảng, tràn số,…
- Luôn kiểm tra trường hợp $P[S] = [\texttt{false},\texttt{true}]$. Để hiểu lý do tại sao hãy đọc Trường hợp 2 của cài đặt.
TH1: tìm $x$ nhỏ nhất mà $P[x] = \texttt{true}$. Dưới đây là đoạn code mẫu viết bằng C++.
bool P[int x] { // Logic của hàm P ở đây return true; // thay giá trị này bằng giá trị đúng logic. } int binary_search[int lo, int hi] { while [lo