Tìm kiếm nhị phân

Trong lĩnh vực khoa học máy tính, tìm kiếm nhị phân (tiếng Anh: binary search) còn được biết đến với các tên gọi khác như tìm kiếm nửa khoảng (half-interval search), tìm kiếm logarit (logarithmic search), hay chặt nhị phân (binary chop). Đây là thuật toán được sử dụng để xác định vị trí của một giá trị trong mảng đã được sắp xếp. Thuật toán so sánh giá trị cần tìm với phần tử ở giữa mảng. Nếu không khớp, nửa mảng không chứa giá trị sẽ bị loại bỏ và tìm kiếm tiếp tục trên nửa còn lại, lặp lại quá trình cho đến khi tìm thấy giá trị hoặc mảng trở nên rỗng.

Tìm kiếm nhị phân có độ phức tạp thời gian là logarit trong trường hợp tệ nhất, với số bước so sánh là $O(\log <!--\; \; -->n)$, với $n$ là số lượng phần tử trong mảng. Phương pháp này nhanh hơn so với tìm kiếm tuyến tính, ngoại trừ khi làm việc với các mảng nhỏ. Mảng cần phải được sắp xếp trước khi áp dụng thuật toán này. Một số cấu trúc dữ liệu như bảng băm có thể tìm kiếm hiệu quả hơn, nhưng tìm kiếm nhị phân vẫn có nhiều ứng dụng như tìm phần tử nhỏ nhất hoặc lớn nhất tiếp theo trong mảng.

Có nhiều biến thể của thuật toán tìm kiếm nhị phân. Ví dụ, phương pháp 'đổ xuống một phần' (fractional cascading) giúp tăng tốc quá trình tìm kiếm nhị phân khi làm việc với giá trị trong nhiều mảng. Phương pháp này giải quyết hiệu quả một số bài toán trong hình học tính toán và nhiều lĩnh vực khác. Thuật toán tìm kiếm mũ (exponential search) mở rộng khả năng của tìm kiếm nhị phân cho các danh sách không giới hạn. Các cấu trúc dữ liệu như cây tìm kiếm nhị phân và B-cây cũng dựa trên nguyên lý tìm kiếm nhị phân.

Thuật toán

Thuật toán tìm kiếm nhị phân được áp dụng cho các mảng đã được sắp xếp theo thứ tự. Thuật toán bắt đầu bằng việc so sánh phần tử ở giữa mảng với giá trị cần tìm. Nếu giá trị này khớp, chỉ số của nó sẽ được trả về. Nếu giá trị cần tìm nhỏ hơn phần tử giữa, quá trình tìm kiếm sẽ tiếp tục trong nửa mảng nhỏ hơn. Nếu giá trị cần tìm lớn hơn phần tử giữa, tìm kiếm sẽ tiếp tục trong nửa mảng lớn hơn. Nhờ vậy, thuật toán có thể loại bỏ một nửa mảng trong mỗi vòng lặp, nơi giá trị cần tìm không thể nằm trong phần đã bị loại bỏ.

Quy trình

Xem xét một mảng $A$ với $n$ phần tử, được sắp xếp theo thứ tự $A_0,A_1,A_2,\dots <!--\; \dots \; -->,A_{n-<!--\; -\; -->1}$, và giá trị cần tìm là $T$, hàm con sau đây sử dụng thuật toán tìm kiếm nhị phân để xác định chỉ số của $T$ trong $A$.

1. Đặt $L$ bằng $0$ và $R$ bằng $n-<!--\; -\; -->1$.
2. Nếu $L>R$, tìm kiếm không thành công.
3. Xác định $m$ (vị trí của phần tử giữa) là giá trị làm tròn xuống của $\frac{L+R}{2}$, tức là số nguyên lớn nhất nhỏ hơn hoặc bằng $\frac{L+R}{2}$.
4. Nếu , gán $L$ bằng $m+1$ và quay lại bước 2.
5. Nếu $A_m>T$, gán $R$ bằng $m-<!--\; -\; -->1$ và quay lại bước 2.
6. Nếu $A_m=<!--\; =\; -->T$, trả về $m$.

Thuật toán tìm kiếm nhị phân có thể được mô tả như sau:

• Đặt $L$ là chỉ số đầu mảng và $R$ là chỉ số cuối mảng.
• So sánh giá trị tại chỉ số giữa của mảng với giá trị cần tìm. Nếu giá trị tại giữa khớp, trả về chỉ số của giá trị đó. Nếu giá trị tại giữa nhỏ hơn giá trị cần tìm, cập nhật chỉ số đầu mảng thành chỉ số giữa + 1. Nếu giá trị tại giữa lớn hơn giá trị cần tìm, cập nhật chỉ số cuối mảng thành chỉ số giữa - 1.
• Tiếp tục lặp lại các bước trên cho đến khi chỉ số đầu mảng lớn hơn chỉ số cuối mảng hoặc giá trị cần tìm được tìm thấy.

hàm tìm_kiếm_nhị_phân(A, n, T) là
    L:= 0
    R:= n − 1
    trong khi L ≤ R thực hiện
        m:= làm_tròn((L + R) / 2)
        nếu A[m] < T thì
            L:= m + 1
        ngược lại nếu A[m] > T thì
            R:= m - 1
        ngược lại:
            trả về m
    trả về không_thành_công

Bên cạnh đó, thuật toán có thể sử dụng giá trị làm tròn lên của $\frac{L+R}{2}$. Điều này có thể làm thay đổi kết quả nếu giá trị cần tìm xuất hiện nhiều lần trong mảng.

Trong quy trình trên, thuật toán kiểm tra xem phần tử ở giữa ($m$) có bằng giá trị cần tìm ($T$) hay không trong mỗi vòng lặp. Một số phương pháp bỏ qua bước này trong mỗi vòng lặp. Trong trường hợp đó, thuật toán chỉ kiểm tra khi còn lại một phần tử duy nhất (khi $L=R$). Điều này giúp vòng lặp so sánh nhanh hơn vì mỗi vòng lặp đã loại bỏ một phép so sánh. Tuy nhiên, phương pháp này có thể làm tăng số lượng vòng lặp trung bình.

Hermann Bottenbruch đã công bố phương pháp bỏ qua bước kiểm tra này lần đầu vào năm 1962.

1. Đặt $L$ bằng $0$ và $R$ bằng $n-<!--\; -\; -->1$.
2. Trong khi $L\ne <!--\; \ne \; -->R$,
   1. Đặt $m$ (vị trí phần tử giữa) thành giá trị làm tròn lên của , tức là số nguyên nhỏ nhất lớn hơn hoặc bằng .
   2. Nếu $A_m>T$, đặt $R$ thành $m-<!--\; -\; -->1$.
   3. Trong trường hợp còn lại, $A_m\le <!--\; \le \; -->T$; gán $L$ bằng $m$.
3. Khi $L=R$, kết thúc tìm kiếm. Nếu $A_L=T$, trả về $L$. Nếu không, tìm kiếm không thành công.

Sử dụng hàm ceil để làm tròn lên, mã giả cho phiên bản này như sau:

function binary_search_alternative(A, n, T) is
 L:= 0
 R:= n − 1
 while L != R do
 m:= ceil((L + R) / 2)
 if A[m] > T then
 R:= m - 1
 else:
 L:= m
 if A[L] = T then
 return L
 return không_thành_công

Phần tử lặp lại

Quy trình tìm kiếm nhị phân trong trường hợp này giống như trước, với sự khác biệt là chúng ta chỉ thay đổi cách tính chỉ số phần tử giữa và không thay đổi cách tiếp cận khác.

Để xác định phần tử gần nhất về bên trái, thực hiện theo các bước sau:

1. Đặt $L$ bằng $0$ và $R$ bằng $n$.
2. Khi ,
3. Gán $m$ (vị trí của phần tử giữa) bằng giá trị làm tròn xuống của , tức là số nguyên lớn nhất nhỏ hơn hoặc bằng .
   1. Nếu , thì gán $L$ bằng $m+1$.
   2. Trong trường hợp ngược lại, nếu $A_m\ge <!--\; \ge \; -->T$, thì gán R {displaystyle R} bằng $m$.
4. Cuối cùng, trả về $L$.

Nếu và $A_L=T$, thì $A_L$ là phần tử đứng xa nhất về bên trái có giá trị bằng $T$. Kể cả khi $T$ không tồn tại trong mảng.

Trong trường hợp ngược lại, nếu , thì $T$ không tồn tại trong mảng.

hàm binary_search_leftmost(A, n, T):
    L:= 0
    R:= n
    khi L < R:
        m:= floor((L + R) / 2)
        nếu A[m] < T:
            L:= m + 1
        ngược lại:
            R:= m
    trả về
  

    
  
   L

Để xác định phần tử xa nhất về phía bên phải, chúng ta có thể thực hiện theo quy trình dưới đây:

1. Đặt $L$ bằng giá trị $0$ và $R$ bằng $n$.
2. Khi ,
3. Đặt $m$ (vị trí phần tử giữa) bằng giá trị của floor của $\frac{L+R}{2}$, tức là số nguyên lớn nhất không vượt quá $\frac{L+R}{2}$.
   1. Nếu $A_m>T$, thì đặt $R$ bằng $m$.
   2. Trường hợp còn lại, $A_m\le <!--\; \le \; -->T$; thì đặt L {\displaystyle L} bằng $m+1$.
4. Trả về $R-<!--\; -\; -->1$.

Nếu $L>0$ và $A_{L-<!--\; -\; -->1}=T$, thì $A_{L-<!--\; -\; -->1}=T$.

Sử dụng hàm floor, mã giả cho phiên bản này được trình bày như sau:

function binary_search_rightmost(A, n, T):
    L:= 0
    R:= n
    while L < R:
        m:= floor((L + R) / 2)
        if A[m] > T:
            R:= m
        else:
            L:= m + 1
    return R - 1

Hiệu năng

Về mặt số lượng phép so sánh, hiệu suất của thuật toán tìm kiếm nhị phân có thể được phân tích bằng cách mô phỏng quá trình hoạt động của thuật toán trên cây nhị phân. Nút gốc của cây là phần tử trung tâm của mảng. Phần tử ở giữa nửa bên trái sẽ trở thành nút con bên trái của nút gốc, trong khi phần tử ở giữa nửa bên phải sẽ trở thành nút con bên phải. Quá trình này tiếp tục cho các phần tử còn lại của cây. Bắt đầu từ nút gốc, thuật toán sẽ duyệt cây con bên trái nếu giá trị cần tìm nhỏ hơn nút hiện tại, hoặc duyệt cây con bên phải nếu giá trị cần tìm lớn hơn.

Trong trường hợp tệ nhất, thuật toán thực hiện $\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->\left(n\right)+1\rfloor <!--\; \rfloor \; -->$ vòng lặp so sánh, trong đó $\lfloor <!--\; \lfloor \; -->\rfloor <!--\; \rfloor \; -->$ là ký hiệu hàm floor, đại diện cho số nguyên lớn nhất nhỏ hơn hoặc bằng giá trị bên trong, và ${\log }_2$ là phép logarit cơ số 2. Điều này xảy ra vì trong trường hợp xấu nhất, thuật toán phải duyệt hết các cấp độ của cây, với số cấp độ trong cây luôn là $\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->\left(n\right)+1\rfloor <!--\; \rfloor \; -->$ cho bất kỳ thuật toán tìm kiếm nhị phân nào.

Trường hợp tệ nhất cũng có thể xảy ra khi giá trị cần tìm không nằm trong mảng. Nếu $n$ có dạng $2^{\mathrm{\alpha <!--\; \alpha \; -->}}-<!--\; -\; -->1$, thì tình huống này luôn xảy ra. Nếu không, thuật toán có thể thực hiện $\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->\left(n\right)+1\rfloor <!--\; \rfloor \; -->$ phép lặp nếu phải duyệt hết các cấp độ của cây. Tuy nhiên, nếu thuật toán kết thúc ở cấp độ sâu thứ hai của cây, quá trình tìm kiếm có thể chỉ cần thực hiện $\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->\left(n\right)\rfloor <!--\; \rfloor \; -->$ vòng lặp, ít hơn trường hợp xấu nhất một vòng.

Nếu các phần tử trong mảng có xác suất tìm kiếm như nhau, thì thuật toán tìm kiếm nhị phân thực hiện trung bình $\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->\left(n\right)\rfloor <!--\; \rfloor \; -->+1-<!--\; -\; -->(2^{\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->\left(n\right)\rfloor <!--\; \rfloor \; -->+1}-<!--\; -\; -->\lfloor <!--\; \lfloor \; -->1\rfloor <!--\; \rfloor \; -->)$ phép so sánh. Trong tình huống xấu nhất, số phép so sánh là $\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->\left(n\right)+1\rfloor <!--\; \rfloor \; -->$ phép so sánh, như đã trình bày ở phần trước.

Mặc dù thuật toán tìm kiếm nhị phân là rất hiệu quả trong tìm kiếm mảng đã sắp xếp, nó không hiệu quả cho mảng không được sắp xếp. Trong trường hợp mảng không được sắp xếp, thuật toán tìm kiếm tuyến tính phải được sử dụng, với độ phức tạp thời gian là O(n). Do đó, để đạt được hiệu suất tối ưu của thuật toán tìm kiếm nhị phân, mảng phải được sắp xếp trước khi thực hiện thuật toán.

Về số lượng phép lặp, không có thuật toán tìm kiếm nào có thể vượt qua tìm kiếm nhị phân về hiệu suất trung bình hay thậm chí trong trường hợp xấu nhất chỉ bằng cách so sánh các phần tử. Cây so sánh cho thuật toán tìm kiếm nhị phân có số bậc tối thiểu, bởi vì mọi bậc trên bậc thấp nhất đều được lấp đầy hoàn toàn. Nếu không, thuật toán có thể loại bỏ một số phần tử trong mỗi phép lặp, dẫn đến việc phải thực hiện nhiều phép lặp hơn trong trường hợp trung bình và tệ nhất. Các thuật toán tìm kiếm dựa trên so sánh cũng gặp phải vấn đề này, vì mặc dù chúng có thể hoạt động nhanh hơn với một số giá trị tìm kiếm cụ thể, nhưng hiệu suất trung bình trên toàn bộ phần tử vẫn kém hơn tìm kiếm nhị phân. Việc chia mảng thành hai nửa giúp thuật toán tìm kiếm nhị phân duy trì kích thước hai mảng con gần như bằng nhau nhất có thể.

Thuật toán tìm kiếm nhị phân yêu cầu ba con trỏ để chỉ đến các phần tử, bất kể kích thước của mảng; có thể là chỉ số các phần tử trong mảng hoặc địa chỉ trong bộ nhớ. Tuy nhiên, thuật toán cần ít nhất $\lceil {\log }_2<!--\; \; -->\left(n\right)\rceil$ bit để mã hóa một con trỏ tới một phần tử trong mảng có $n$ phần tử. Do đó, độ phức tạp không gian của thuật toán tìm kiếm nhị phân là $O(\log <!--\; \; -->n)$. Thêm vào đó, thuật toán cần $O\left(n\right)$ không gian để lưu trữ mảng.

Trường hợp trung bình

Số lượng phép lặp trung bình mà thuật toán thực hiện phụ thuộc vào xác suất mỗi phần tử được tìm. Trường hợp trung bình khi tìm kiếm thành công và không thành công là khác nhau. Giả định rằng mỗi phần tử có xác suất được tìm như nhau nếu tìm kiếm thành công. Trong trường hợp tìm kiếm không thành công, các khoảng giữa và ngoài các phần tử có xác suất được tìm tương đương. Trường hợp trung bình khi tìm kiếm thành công là số phép lặp cần thực hiện để tìm tất cả các phần tử chính xác một lần, chia cho $n$, tổng số phần tử trong mảng. Trong trường hợp tìm kiếm không thành công, là số phép lặp cần thực hiện để kiểm tra tất cả các khoảng chính xác một lần, chia cho $n+1$ khoảng.

Khi sử dụng cây nhị phân để biểu diễn, một lần tìm kiếm thành công có thể được mô tả như một con đường từ gốc tới nút mục tiêu, gọi là đường đi trong (internal path). Độ dài của con đường này là số cạnh mà nó đi qua. Số phép lặp thực hiện trong một lần tìm kiếm, nếu độ dài con đường tương ứng là $l$, là $l+1$, bao gồm cả bước lặp đầu tiên. Độ dài đường đi trong (internal path length) là tổng độ dài của tất cả các con đường trong. Vì chỉ có một con đường duy nhất từ gốc đến bất kỳ nút nào, mỗi con đường này tương ứng với một lần tìm kiếm phần tử. Nếu có $n$ phần tử, và độ dài đường trong là $I\left(n\right)$, thì số phép lặp trung bình cho một lần tìm kiếm thành công là $T\left(n\right)=1+\frac{I\left(n\right)}{n}$, với một bước lặp ban đầu đã được tính thêm.

Vì thuật toán tìm kiếm nhị phân là tối ưu cho việc tìm kiếm bằng so sánh, bài toán có thể được đơn giản hóa thành việc tính độ dài đường đi trong tối thiểu của tất cả các cây nhị phân với $n$ nút, được tính như sau:

$I\left(n\right)=\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}\lfloor {\log }_2<!--\; \; -->\left(k\right)\rfloor$

Ví dụ, với một mảng gồm 7 phần tử, phần tử gốc cần một phép lặp, hai phần tử nằm dưới gốc yêu cầu hai phép lặp, và bốn phần tử tiếp theo cần gần ba phép lặp. Trong trường hợp này, tổng độ dài của các đường đi trong là:

$\underset{k=1}{\overset{7}{\sum <!--\; \sum \; -->}}\lfloor {\log }_2<!--\; \; -->\left(k\right)\rfloor =0+2\left(1\right)+4\left(2\right)=2+8=10$

Số lần lặp trung bình được tính là $1+\frac{10}{7}=2\frac{3}{7}$ theo công thức tính trung bình. Tổng $I\left(n\right)$ có thể được đơn giản hóa thành:

$I\left(n\right)=\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}\lfloor {\log }_2<!--\; \; -->\left(k\right)\rfloor =(n+1)\lfloor {\log }_2<!--\; \; -->(n+1)\rfloor -<!--\; -\; -->2^{\lfloor {\log }_2<!--\; \; -->(n+1)\rfloor +1}+2$

Thay thế $I\left(n\right)$ vào trong phương trình $T\left(n\right)$:

$T\left(n\right)=1+\frac{(n+1)\lfloor {\log }_2<!--\; \; -->(n+1)\rfloor }{2}+2=2+\frac{(n+1)\lfloor {\log }_2<!--\; \; -->(n+1)\rfloor }{2}=\frac{(n+1)\lfloor {\log }_2<!--\; \; -->(n+1)\rfloor }{2}+2$

Nếu $n$ là một số nguyên, thì phương trình này có thể được coi như phương trình trung bình cho một lần tìm kiếm thành công, như đã nêu ở trên.

Chúng ta có thể diễn tả một lần tìm kiếm không thành công bằng cách thêm các nút ngoài vào cây, hình thành nên cây nhị phân mở rộng. Nếu một nút bên trong hoặc một nút hiện có trong cây có ít hơn hai nút con, chúng ta sẽ thêm các nút con bổ sung gọi là các nút ngoài, để đảm bảo mỗi nút bên trong đều có hai nút con. Như vậy, một tìm kiếm không thành công có thể được biểu diễn như là một đường đi đến một nút ngoài, trong đó nút cha là phần tử duy nhất còn lại trong lần lặp cuối cùng. Đường đi ngoài (external path) là con đường từ gốc đến một nút ngoài. Độ dài đường đi ngoài (external path length) là tổng độ dài của tất cả các đường đi ngoài độc nhất. Nếu số phần tử là $n$ và độ dài đường đi ngoài là $E\left(n\right)$, thì số phép lặp trung bình cho một tìm kiếm không thành công là $T^{\prime }\left(n\right)=\frac{E\left(n\right)}{n+1}$, bao gồm một phép lặp đầu tiên. Công thức này tính toán độ dài đường đi ngoài chia cho $n+1$ thay vì $n$, vì có $n+1$ đường đi ngoài đại diện cho các khoảng giữa và ngoài các phần tử trong mảng.

Tương tự, bài toán có thể được đơn giản hóa thành việc tính toán độ dài đường đi ngoài tối thiểu của tất cả các cây nhị phân có $n$ nút. Đối với tất cả các cây nhị phân, độ dài đường đi ngoài bằng độ dài đường đi trong cộng với $2n$. Thay thế $I\left(n\right)$ vào công thức, ta có:

$E\left(n\right)=I\left(n\right)+2n=\left[(n+1)\lfloor {\log }_2<!--\; \; -->(n+1)\rfloor -<!--\; -\; -->2^{\lfloor {\log }_2<!--\; \; -->(n+1)\rfloor +1}+2\right)-<!--\; -\; -->2$

Thay $E\left(n\right)$ vào công thức tính $T^{\prime }\left(n\right)$, ta có thể tính toán trường hợp trung bình cho những lần tìm kiếm không thành công.

Trong tìm kiếm nhị phân, mỗi vòng lặp thực hiện từ một đến hai phép so sánh để kiểm tra phần tử giữa có khớp với giá trị cần tìm. Nếu tất cả các phần tử đều có xác suất như nhau, mỗi vòng lặp thực hiện trung bình 1,5 phép so sánh. Một cách tiếp cận khác là kiểm tra phần tử giữa ở cuối mỗi lần tìm kiếm. Cách này giúp giảm 0,5 phép so sánh trung bình mỗi lần lặp, do đó tiết kiệm thời gian trên hầu hết các máy tính. Tuy nhiên, cách này lại yêu cầu thực hiện số phép lặp tối đa cho mỗi lần tìm kiếm, làm tăng trung bình một phép lặp cho mỗi tìm kiếm. Vì mỗi vòng lặp so sánh chỉ được thực hiện $\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->\left(n\right)+1\rfloor <!--\; \rfloor \; -->$ lần trong trường hợp xấu nhất, việc tiết kiệm thời gian trên mỗi phép lặp không thể bù đắp cho việc tăng thêm một phép lặp khi $n$ không đủ lớn.

Thời gian chạy và hiệu quả sử dụng bộ nhớ đệm

Khi phân tích hiệu suất của thuật toán, cần lưu ý đến thời gian so sánh giữa hai phần tử. Đối với số nguyên và chuỗi ký tự, thời gian này tăng theo cấp số tuyến tính với độ dài mã hóa của các phần tử, thường là số bit. Ví dụ, việc so sánh hai số nguyên 64 bit mất nhiều thời gian gấp đôi so với hai số nguyên 32 bit. Trường hợp xấu nhất xảy ra khi hai số nguyên bằng nhau. Điều này trở nên quan trọng hơn khi độ dài mã hóa của các phần tử lớn, chẳng hạn như so sánh các số nguyên lớn hơn hoặc các chuỗi ký tự dài, gây tốn thời gian hơn. Hơn nữa, việc so sánh các giá trị số thực (số thông dụng nhất cho số thực) thường chậm hơn so với số nguyên hay chuỗi ký tự ngắn.

Hầu hết các kiến trúc máy tính hiện đại đều có bộ nhớ cache riêng biệt bên trong bộ vi xử lý, tách biệt khỏi RAM. Bộ nhớ cache, nằm gần bộ vi xử lý, cho phép truy cập nhanh hơn nhưng có dung lượng nhỏ hơn so với RAM. Bộ vi xử lý thường lưu trữ địa chỉ các vùng bộ nhớ đã được truy cập gần đây cùng với các vùng lân cận. Ví dụ, khi truy cập một phần tử trong mảng, phần tử đó cùng với các phần tử gần kề có thể được lưu trữ trong bộ nhớ cache, giúp tăng tốc truy xuất các phần tử kế tiếp (tính địa phương trong truy xuất - locality of reference). Trong trường hợp mảng đã được sắp xếp, tìm kiếm nhị phân có thể phải truy cập các vùng bộ nhớ xa hơn nếu mảng lớn, khác với các thuật toán như tìm kiếm tuyến tính hay dò tuyến tính trong bảng băm, truy cập các phần tử theo thứ tự. Điều này làm cho thời gian chạy của thuật toán tăng nhẹ với các mảng lớn trên nhiều hệ thống.

Tìm kiếm nhị phân trong các hệ thống khác

Việc áp dụng tìm kiếm nhị phân cho các mảng đã sắp xếp trở nên kém hiệu quả khi phải kết hợp với các thao tác chèn và xóa, mỗi thao tác này yêu cầu thời gian $O\left(n\right)$. Hơn nữa, việc yêu cầu phải sắp xếp các mảng có thể làm phức tạp việc sử dụng bộ nhớ, đặc biệt khi các phần tử thường xuyên được chèn vào. Một số cấu trúc dữ liệu khác có thể hỗ trợ các thao tác chèn và xóa hiệu quả hơn. Tìm kiếm nhị phân có thể được sử dụng để thực hiện các so khớp chính xác và thao tác quan hệ tập hợp (xác định giá trị cần tìm có thuộc một tập hợp lớn không). Hai bài toán này cũng có thể thực hiện nhanh hơn trên các cấu trúc dữ liệu khác. Tuy nhiên, khác với các hệ thống tìm kiếm khác, tìm kiếm nhị phân hiệu quả hơn trong phép so khớp xấp xỉ, thường thực hiện trong thời gian $O(\log <!--\; \; -->n)$ bất kể kiểu hay cấu trúc của các giá trị. Ngoài ra, một số phép toán như tìm phần tử nhỏ nhất và lớn nhất có thể được thực hiện hiệu quả hơn trên các mảng đã sắp xếp.

Tìm kiếm tuyến tính

Tìm kiếm tuyến tính là một thuật toán đơn giản: nó sẽ kiểm tra từng bản ghi một cho đến khi tìm thấy giá trị cần thiết. Thuật toán này có thể áp dụng trên danh sách liên kết, giúp thực hiện các thao tác chèn và xóa nhanh chóng hơn so với mảng. Tìm kiếm nhị phân, ngược lại, thường nhanh hơn tìm kiếm tuyến tính trên các mảng đã sắp xếp, trừ khi mảng nhỏ, mặc dù trước khi thực hiện tìm kiếm nhị phân, mảng cần được sắp xếp. Các thuật toán sắp xếp dựa trên so sánh phần tử, như sắp xếp nhanh và sắp xếp trộn, cần ít nhất $O(n\log <!--\; \; -->n)$ so sánh trong trường hợp xấu nhất. Khác với tìm kiếm tuyến tính, tìm kiếm nhị phân có thể thực hiện tìm kiếm xấp xỉ một cách hiệu quả. Một số thao tác như tìm phần tử nhỏ nhất và lớn nhất chỉ có thể thực hiện hiệu quả khi mảng đã được sắp xếp.

Cây

Cây tìm kiếm nhị phân là một cấu trúc dữ liệu dạng cây nhị phân dựa trên nguyên lý của tìm kiếm nhị phân. Các bản ghi trong cây được sắp xếp theo thứ tự, và có thể tìm kiếm bằng thuật toán tương tự như tìm kiếm nhị phân, với thời gian trung bình là logarit. Các thao tác chèn và xóa trong cây tìm kiếm nhị phân cũng mất thời gian logarit trung bình, nhanh hơn so với thao tác trên các mảng đã sắp xếp, đồng thời các thao tác như truy vấn khoảng và xấp xỉ có thể thực hiện trên cây nhị phân cũng như trên mảng đã sắp xếp.

Tuy nhiên, tìm kiếm nhị phân thường hiệu quả hơn so với cây tìm kiếm nhị phân, vì cây nhị phân thường không hoàn toàn cân bằng, dẫn đến hiệu suất kém hơn so với tìm kiếm nhị phân. Điều này vẫn đúng ngay cả với cây tìm kiếm nhị phân tự cân bằng, vì chúng hiếm khi tạo ra cây với số bậc tối ưu. Ngoài các cây tìm kiếm nhị phân cân bằng, số lượng nút ít trong cây có thể gây mất cân bằng nghiêm trọng, làm tăng số phép so sánh cần thiết trong trường hợp trung bình và tệ nhất lên đến $n$. Cây tìm kiếm nhị phân cũng đòi hỏi nhiều không gian hơn so với mảng đã sắp xếp.

Cây tìm kiếm nhị phân rất hiệu quả khi cần tìm kiếm nhanh trong các ổ cứng ngoài, nhờ khả năng xây dựng hiệu quả trong hệ thống tập tin. B-cây, một sự mở rộng của cấu trúc này, thường được sử dụng để tổ chức dữ liệu trong các cơ sở dữ liệu và hệ thống tập tin dài hạn.

Băm

Trong các mảng kết hợp, bảng băm là một cấu trúc dữ liệu sử dụng hàm băm để ánh xạ các khóa thành bản ghi, thường hoạt động nhanh hơn so với tìm kiếm nhị phân trên mảng đã được sắp xếp. Hầu hết các triển khai bảng băm yêu cầu thời gian hằng số trung bình. Tuy nhiên, băm không hiệu quả cho các bài toán so khớp xấp xỉ, chẳng hạn như tìm khóa nhỏ nhất tiếp theo, khóa lớn nhất tiếp theo và khóa gần nhất, vì khi tìm kiếm thất bại, chỉ biết rằng khóa không có trong bất kỳ bản ghi nào. Tìm kiếm nhị phân là giải pháp lý tưởng cho những bài toán này, với thời gian chạy logarit và cũng hỗ trợ so khớp xấp xỉ. Một số phép toán như tìm phần tử nhỏ nhất và lớn nhất có thể thực hiện hiệu quả trên mảng đã sắp xếp nhưng không trên bảng băm.

Các thuật toán quan hệ tập hợp

Một khía cạnh quan trọng của tìm kiếm là quan hệ tập hợp. Các thuật toán như tìm kiếm nhị phân có thể dùng để thực hiện quan hệ tập hợp. Một số thuật toán khác phù hợp hơn cho việc này. Mảng bit, thường được sử dụng khi số khóa có giới hạn, lưu trữ các bit một cách compact, với mỗi bit đại diện cho một khóa trong một khoảng xác định. Mảng bit hoạt động rất nhanh, trong thời gian $O\left(1\right)$. Mảng Judy1, một loại mảng Judy, có khả năng xử lý các khóa 64-bit một cách hiệu quả.

Khi cần kết quả xấp xỉ, bộ lọc Bloom là một lựa chọn hiệu quả. Đây là một cấu trúc dữ liệu xác suất dựa trên hàm băm, sử dụng mảng bit kết hợp với nhiều hàm băm để lưu trữ các khóa. Bộ lọc Bloom chiếm ít không gian hơn so với mảng bit trong hầu hết các trường hợp và hoạt động không chậm hơn nhiều: với $k$ hàm băm, thời gian kiểm tra phần tử chỉ cần $O\left(k\right)$. Tuy nhiên, bộ lọc Bloom có thể đưa ra kết quả dương tính giả.

Các cấu trúc dữ liệu khác

Có nhiều cấu trúc dữ liệu khác có thể cải thiện hiệu suất của tìm kiếm nhị phân trong một số tình huống và cho cả các thao tác khác trên mảng đã sắp xếp. Ví dụ, các cấu trúc như cây van Emde Boas, fusion trees, trie và mảng bit có thể thực hiện các phép tìm kiếm, so khớp xấp xỉ và thao tác khác trên mảng đã sắp xếp nhanh hơn tìm kiếm nhị phân. Những cấu trúc dữ liệu chuyên biệt này thường chỉ nhanh hơn vì chúng tận dụng các đặc tính của các khóa trong một điều kiện nhất định (thường là các số nguyên nhỏ). Nếu không đáp ứng điều kiện đó, thời gian chạy hoặc không gian cần thiết có thể tăng lên đáng kể. Tuy nhiên, với các khóa có thể sắp xếp, các thao tác này có thể thực hiện hiệu quả trên mảng đã sắp xếp mà không phụ thuộc vào loại khóa. Một số cấu trúc như mảng Judy kết hợp nhiều phương pháp để đơn giản hóa điều kiện, giữ được hiệu quả và khả năng thực hiện so khớp xấp xỉ.

Biến thể

Tìm kiếm nhị phân đồng nhất

Thay vì lưu các giới hạn trên và dưới, tìm kiếm nhị phân đồng nhất giữ khoảng cách từ chỉ số của phần tử giữa trong vòng lặp này tới vòng lặp tiếp theo. Thuật toán xây dựng một bảng dò tìm (lookup table) để lưu các khoảng cách này. Ví dụ, với mảng [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], phần tử giữa ($m$) là 6. Trong trường hợp này, phần tử giữa của mảng con bên trái ([1, 2, 3, 4, 5]) là 3 và phần tử giữa của mảng con bên phải ([7, 8, 9, 10, 11]) là 9. Thuật toán lưu giá trị 3, tức là khoảng cách từ hai chỉ số con đến phần tử giữa ban đầu là 6. Để giảm không gian tìm kiếm, thuật toán điều chỉnh lượng thay đổi này so với chỉ số của phần tử giữa. Tìm kiếm nhị phân đồng nhất có thể hoạt động nhanh hơn trên các hệ thống không tính được điểm giữa hiệu quả, như trên máy tính thập phân.

Tìm kiếm mũ

Tìm kiếm mũ là một phương pháp mở rộng của tìm kiếm nhị phân, đặc biệt hữu ích với các danh sách không có giới hạn. Thuật toán bắt đầu bằng cách tìm phần tử đầu tiên có chỉ số là một lũy thừa của hai và có giá trị lớn hơn giá trị cần tìm. Chỉ số này sau đó được đặt làm giới hạn trên và tìm kiếm tiếp tục dưới dạng tìm kiếm nhị phân. Quá trình này yêu cầu $\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->x+1\rfloor <!--\; \rfloor \; -->$ vòng lặp trước khi bắt đầu tìm kiếm nhị phân, với nhiều nhất $\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->x\rfloor <!--\; \rfloor \; -->$ vòng lặp khi thực hiện tìm kiếm nhị phân, với $x$ là vị trí của giá trị cần tìm. Tìm kiếm mũ cũng có thể áp dụng cho các danh sách có giới hạn, nhưng hiệu quả hơn khi giá trị cần tìm nằm gần đầu mảng.

Tìm kiếm nội suy

Thay vì tính điểm giữa, tìm kiếm nội suy ước lượng vị trí của giá trị cần tìm dựa vào các giá trị lớn nhất, nhỏ nhất và kích thước của mảng. Thuật toán này dựa trên thực tế rằng vị trí giữa có thể không phải là ước lượng tốt nhất trong nhiều trường hợp. Ví dụ, nếu giá trị cần tìm gần với phần tử lớn nhất trong mảng, khả năng cao nó sẽ nằm gần cuối mảng.

Một loại hàm nội suy phổ biến là nội suy tuyến tính. Nếu $A$ là mảng cần tìm, $L,R$ là các giới hạn dưới và trên, và $T$ là giá trị cần tìm, thì vị trí ước lượng của giá trị cần tìm sẽ nằm ở khoảng $(T-<!--\; -\; -->A_L)/(A_R-<!--\; -\; -->A_L)$ khoảng cách giữa $L$ và $R$. Khi sử dụng nội suy tuyến tính và các phần tử trong mảng phân phối đồng đều hoặc gần đồng đều, tìm kiếm nội suy thực hiện $O(\log <!--\; \; -->\log <!--\; \; -->n)$ phép so sánh.

Trong thực tế, tìm kiếm nội suy thường chậm hơn tìm kiếm nhị phân với các mảng nhỏ vì nó yêu cầu nhiều tính toán hơn. Độ phức tạp thời gian của thuật toán này tăng chậm hơn so với tìm kiếm nhị phân, nhưng lợi thế này chỉ đáng kể khi mảng có kích thước lớn.

Đổ xuống một phần

Kỹ thuật đổ xuống một phần giúp tăng tốc tìm kiếm nhị phân với cùng một giá trị trong nhiều mảng khác nhau đã được sắp xếp. Nếu thực hiện tìm kiếm tách rời trong từng mảng, ta sẽ cần $O(k\log <!--\; \; -->n)$ thời gian, trong đó $k$ là số lượng mảng. Phương pháp đổ xuống một phần giảm thời gian tìm kiếm xuống còn $O(k+\log <!--\; \; -->n)$ bằng cách lưu trữ thông tin về từng phần tử và vị trí của chúng trong các mảng khác.

Phương pháp đổ xuống một phần được phát triển ban đầu để giải quyết các vấn đề trong hình học tính toán. Ngày nay, kỹ thuật này đã được ứng dụng rộng rãi trong các lĩnh vực khác, như khai phá dữ liệu và định tuyến giao thức Internet.

Tổng quát với đồ thị

Tìm kiếm nhị phân có thể được mở rộng để làm việc với nhiều loại đồ thị khác nhau, trong đó giá trị cần tìm được lưu trữ tại một đỉnh thay vì trong một mảng. Cây tìm kiếm nhị phân là một ví dụ về sự mở rộng này—khi một đỉnh trong cây được kiểm tra, thuật toán sẽ xác định xem đỉnh đó có phải là giá trị cần tìm hay không, hoặc tìm kiếm trong cây con chứa giá trị đó. Quá trình này có thể được mở rộng hơn cho đồ thị vô hướng có trọng số dương: khi truy vấn một đỉnh, thuật toán sẽ xác định đỉnh đó có phải là đỉnh cần tìm không, hoặc tìm cạnh kề nằm trong đường đi ngắn nhất từ đỉnh hiện tại đến đỉnh cần tìm. Trong trường hợp đồ thị là một đường đi, thuật toán tìm kiếm nhị phân tiêu chuẩn là một ví dụ cụ thể. Tương tự, trong các cây tìm kiếm nhị phân, các cạnh thuộc cây con bên trái hoặc phải được kiểm tra nếu đỉnh không phải là đỉnh cần tìm. Đối với mọi đồ thị vô hướng có trọng số dương, luôn có thuật toán có thể tìm một đỉnh với $O(\log <!--\; \; -->n)$ phép truy vấn trong trường hợp xấu nhất.

Tìm kiếm nhị phân với nhiễu

Các thuật toán tìm kiếm nhị phân với nhiễu (noisy binary search) được thiết kế để giải quyết các tình huống mà việc so sánh các phần tử không hoàn toàn chính xác. Mỗi lần so sánh giữa hai phần tử có thể bị sai lệch với một xác suất nhất định. Tìm kiếm nhị phân với nhiễu có thể xác định vị trí chính xác của giá trị cần tìm với một xác suất cho trước, nhằm đảm bảo độ tin cậy của kết quả. Trung bình, mỗi lần tìm kiếm nhị phân với nhiễu yêu cầu ít nhất $(1-<!--\; -\; -->\mathrm{\tau <!--\; \tau \; -->})\frac{{\log }_2<!--\; \; -->\left(n\right)}{H\left(p\right)}-<!--\; -\; -->\frac{10}{H\left(p\right)}$ phép so sánh, với $H\left(p\right)=-<!--\; -\; -->p{\log }_2<!--\; \; -->\left(p\right)-<!--\; -\; -->(1-<!--\; -\; -->p){\log }_2<!--\; \; -->(1-<!--\; -\; -->p)$ là hàm entropy nhị phân và $\mathrm{\tau <!--\; \tau \; -->}$ là xác suất một lần tìm kiếm cho ra kết quả sai. Bài toán tìm kiếm nhị phân với nhiễu có thể được xem như một phiên bản của trò chơi Rényi-Ulam, một biến thể của trò chơi Hai mươi câu hỏi với các câu trả lời có thể bị sai.

Tìm kiếm nhị phân lượng tử

Trong các máy tính cổ điển, tìm kiếm nhị phân bị giới hạn bởi số phép lặp tối đa là $\lfloor <!--\; \lfloor \; -->{\log }_2<!--\; \; -->n+1\rfloor <!--\; \rfloor \; -->$ trong trường hợp tồi tệ nhất. Tuy nhiên, các thuật toán lượng tử cho tìm kiếm nhị phân vẫn giữ giới hạn này ở mức ${\log }_2<!--\; \; -->n$ phép truy vấn (tương đương số vòng lặp trong máy tính cổ điển), nhưng với hệ số nhỏ hơn, giúp giảm độ phức tạp thời gian. Một thuật toán tìm kiếm nhị phân lượng tử chính xác—tức là luôn cho kết quả đúng—cần ít nhất $\frac{1}{\mathrm{\pi <!--\; \pi \; -->}}(\ln <!--\; \; -->n-<!--\; -\; -->1)\approx <!--\; \approx \; -->0.22{\log }_2<!--\; \; -->n$ phép truy vấn trong trường hợp tồi tệ nhất, trong đó $\ln$ là hàm logarit tự nhiên. Một phương pháp chính xác cho tìm kiếm nhị phân lượng tử có thể thực hiện trong $4{\log }_{605}<!--\; \; -->n\approx <!--\; \approx \; -->0.433{\log }_2<!--\; \; -->n$ phép truy vấn trong trường hợp xấu nhất. So với các thuật toán khác, thuật toán Grover là phương pháp lượng tử tối ưu cho tìm kiếm trong danh sách chưa sắp xếp, với $O\left(\sqrt{n}\right)$ phép truy vấn.

Lịch sử

Ý tưởng sắp xếp danh sách để cải thiện tốc độ tìm kiếm đã xuất hiện từ lâu. Ví dụ, tấm bảng Inakibit-Anu từ thời Babylon vào khoảng k. 200 TCN là một trong những ví dụ sớm nhất. Nó chứa khoảng 500 số hệ thập lục phân và các số nghịch đảo của chúng được sắp xếp theo thứ tự từ điển, làm cho việc tìm kiếm trở nên dễ dàng hơn. Tương tự, trên Quần đảo Aegean, các danh sách tên cũng được sắp xếp theo chữ cái đầu tiên. Cuốn từ điển Latin Catholicon, hoàn thành vào năm 1286 SCN, là tài liệu đầu tiên mô tả các quy tắc sắp xếp từ theo thứ tự bảng chữ cái thay vì chỉ dựa vào vài ký tự đầu tiên.

Năm 1946, John Mauchly đã lần đầu tiên đề cập đến thuật toán tìm kiếm nhị phân trong các bài giảng Moore School, khóa học máy tính tại Đại học Pennsylvania. Vào năm 1957, William Wesley Peterson công bố phương pháp đầu tiên cho thuật toán tìm kiếm nội suy. Trước năm 1960, tất cả các thuật toán tìm kiếm nhị phân chỉ hoạt động với các mảng có kích thước dạng $2^{\mathrm{\alpha <!--\; \alpha \; -->}}-<!--\; -\; -->1$ cho đến năm 1960, khi Derrick Henry Lehmer phát triển thuật toán tìm kiếm nhị phân có thể xử lý mọi mảng. Năm 1962, Hermann Bottenbruch giới thiệu thuật toán tìm kiếm nhị phân bằng ngôn ngữ ALGOL 60, trong đó bước kiểm tra phần tử giữa được đưa xuống cuối để tăng số phép lặp trung bình thêm một, nhưng giảm được một phép so sánh mỗi vòng lặp. Thuật toán tìm kiếm nhị phân đồng đều được A. K. Chandra phát triển tại Đại học Stanford vào năm 1971. Đến năm 1986, Bernard Chazelle và Leonidas J. Guibas đã giới thiệu phương pháp đổ xuống một phần (fractional cascading) nhằm giải quyết nhiều vấn đề trong tìm kiếm hình học tính toán.

Thư viện hỗ trợ

Các ngôn ngữ lập trình đều có thư viện chuẩn với các hàm thực hiện tìm kiếm nhị phân:

• Trong C, hàm bsearch() được cung cấp bởi thư viện chuẩn và thường sử dụng thuật toán tìm kiếm nhị phân, dù tiêu chuẩn không bắt buộc.
• Thư viện Standard Template Library của C++ cung cấp các hàm binary_search(), lower_bound(), upper_bound() và equal_range().
• COBOL có động từ SEARCH ALL để thực hiện tìm kiếm nhị phân trên các bảng đã được sắp xếp trong COBOL.
• Thư viện chuẩn sort của Go cung cấp các hàm Search, SearchInts, SearchFloat64s và SearchStrings, hỗ trợ tìm kiếm nhị phân cho nhiều loại dữ liệu khác nhau như số nguyên, số thập phân, và chuỗi ký tự.
• Java cung cấp các phương thức static binarySearch() trong lớp Arrays và Collections trong gói java.util, cho phép tìm kiếm nhị phân trên mảng và danh sách.
• .NET Framework 2.0 của Microsoft cung cấp các phiên bản static của thuật toán tìm kiếm nhị phân trong các lớp cơ bản của collection, ví dụ phương thức BinarySearch<T>(T[] array, T value) trong System.Array
• Framework Cocoa của Objective-C trên Mac OS X từ phiên bản 10.6 trở đi cung cấp phương thức NSArray -indexOfObject:inSortedRange:options:usingComparator:. Framework Core Foundation C của Apple cũng có hàm CFArrayBSearchValues().
• Mô-đun bisect được cung cấp bởi Python.
• Lớp Array của Ruby bao gồm phương thức bsearch với khả năng so khớp xấp xỉ.

Ghi chú và tài liệu tham khảo

Ghi chú

Chú giải

Danh mục tài liệu