Xem mã nguồn của Tìm kiếm nhị phân

{{Về|tìm kiếm trên một mảng hữu hạn đã được sắp xếp|tìm kiếm các giá trị của một hàm liên tục|phương pháp chia đôi}}{{Mô tả ngắn|Thuật toán tìm kiếm tìm vị trí của một giá trị cần tìm trong một mảng đã được sắp xếp}}{{Infobox algorithm
|class=[[Thuật toán tìm kiếm]]
|image=Binary Search Depiction.svg
|caption=Minh họa thuật toán tìm kiếm nhị phân, trong đó 7 là giá trị cần tìm
|data=[[Mảng (cấu trúc dữ liệu)|Mảng]]
|time=[[Kí hiệu O lớn#Orders of common functions|''O''(log ''n'')]]
|space = [[Kí hiệu O lớn#Orders of common functions|''O''(1)]]
|best-time=[[Kí hiệu O lớn#Orders of common functions|''O''(1)]]
|average-time=[[Kí hiệu O lớn#Orders of common functions|''O''(log ''n'')]]
|optimal=Có
}}
Trong [[khoa học máy tính]], '''tìm kiếm nhị phân''' ({{lang-en|binary search}}), còn gọi là '''tìm kiếm nửa khoảng''' (''half-interval search''),<ref name="Williams1976">{{cite conference|last1=Williams, Jr.|first1=Louis F.|title=A modification to the half-interval search (binary search) method|conference=Proceedings of the 14th ACM Southeast Conference|date=ngày 22 tháng 4 năm 1976|pages=95–101|doi=10.1145/503561.503582|url=https://dl.acm.org/citation.cfm?doid=503561.503582|publisher=ACM|access-date =ngày 29 tháng 6 năm 2018|archive-url=https://web.archive.org/web/20170312215255/http://dl.acm.org/citation.cfm?doid=503561.503582|archive-date=ngày 12 tháng 3 năm 2017|url-status=live|df=dmy-all}}</ref> '''tìm kiếm logarit''' (''logarithmic search''),{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}} hay '''chặt nhị phân''' (''binary chop''),{{Sfn|Butterfield|Ngondi|2016|p=46}} là một [[thuật toán tìm kiếm]] xác định vị trí của một giá trị cần tìm trong một mảng đã được sắp xếp.{{Sfn|Cormen|Leiserson|Rivest|Stein|2009|p=39}}<ref>{{MathWorld |title=Binary search |id=BinarySearch}}</ref> Thuật toán tiến hành so sánh giá trị cần tìm với phần tử đứng giữa mảng. Nếu hai giá trị không bằng nhau, phần nửa mảng không chứa giá trị cần tìm sẽ bị bỏ qua và tiếp tục tìm kiếm trên nửa còn lại, một lần nữa lấy phần tử ở giữa và so sánh với giá trị cần tìm, cứ thế lặp lại cho đến khi tìm thấy giá trị đó. Nếu phép tìm kiếm kết thúc khi nửa còn lại trống thì giá trị cần tìm không có trong mảng.

Tìm kiếm nhị phân chạy theo [[Độ phức tạp thời gian#Thời gian logarit|thời gian logarit]] trong [[Trường hợp tốt nhất, tệ nhất và trung bình|trường hợp tệ nhất]], thực hiện <math>O(\log n)</math> bước so sánh, trong đó <math>n</math> là số phần tử trong mảng, <math>O</math> là [[kí hiệu O lớn]], và <math>\log</math> là phép toán [[logarit]].<ref name="FloresMadpis1971">{{chú thích tạp chí|last1=Flores|first1=Ivan|last2=Madpis|first2=George|title=Average binary search length for dense ordered lists|journal=[[Communications of the ACM]]|date=ngày 1 tháng 9 năm 1971|volume=14|issue=9|pages=602–603|issn=0001-0782|doi=10.1145/362663.362752|bibcode=1985CACM...28...22S}}</ref> Thuật toán tìm kiếm nhị phân nhanh hơn so với [[tìm kiếm tuyến tính]], ngoại trừ các trường hợp mảng có kích thước nhỏ. Tuy nhiên, mảng phải được sắp xếp trước khi áp dụng tìm kiếm nhị phân. Một số [[cấu trúc dữ liệu]] chuyên dụng được thiết kế cho việc tìm kiếm nhanh, ví dụ như [[bảng băm]], có thể thực hiện tìm hiệu quả hơn tìm kiếm nhị phân. Tuy nhiên, thuật toán này có thể dùng để giải quyết nhiều loại vấn đề hơn, như tìm phần tử nhỏ nhất hoặc lớn nhất tiếp theo trong mảng so với giá trị cho trước, kể cả khi nó không có trong mảng.

Có nhiều biến thể của phép tìm kiếm nhị phân. Cụ thể, phương pháp "đổ xuống một phần" (''fractional cascading'') 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. Phương pháp này cho phép giải quyết hiệu quả một số vấn đề về tìm kiếm 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 tìm kiếm nhị phân sang các danh sách không có giới hạn. Các cấu trúc dữ liệu [[cây tìm kiếm nhị phân]] và [[B-cây]] được xây dựng dựa trên tìm kiếm nhị phân.

== Thuật toán ==
Thuật toán tìm kiếm nhị phân hoạt động trên các mảng đã được sắp xếp. Thuật toán bắt đầu bằng việc so sánh một phần tử đứng chính giữa mảng với giá trị cần tìm. Nếu bằng nhau, vị trí của nó trong mảng sẽ được trả về. Nếu giá trị cần tìm nhỏ hơn phần tử này, quá trình tìm kiếm tiếp tục ở nửa nhỏ hơn của mảng. Nếu giá trị cần tìm lớn hơn phần tử ở giữa, quá trình tìm kiếm tiếp tục ở nửa lớn hơn của mảng. Bằng cách này, ở mỗi phép lặp thuật toán có thể loại bỏ nửa mảng mà giá trị cần tìm chắc chắn không xuất hiện.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Algorithm B"}}

===Quy trình===
Cho một mảng <math>A</math> có <math>n</math> phần tử với các giá trị hoặc [[bản ghi]] <math>A_0,A_1,A_2,\ldots,A_{n-1}</math>đã được sắp xếp sao cho <math>A_0 \leq A_1 \leq A_2 \leq \cdots \leq A_{n-1}</math>, và giá trị cần tìm <math>T</math>, [[chương trình con]] sau đây sử dụng tìm kiếm nhị phân để tìm chỉ số của <math>T</math> trong <math>A</math>.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Algorithm B"}}
# Gán <math>L</math> với giá trị <math>0

</math> và <math>R</math> với giá trị <math>n-1</math>.
# Nếu <math>L>R</math>, quá trình tìm kiếm thất bại.
# Gán <math>m</math> (vị trí của phần tử đứng giữa) với giá trị [[Phần nguyên|floor]] của <math>\frac{L+R}{2}</math>, tức là số nguyên lớn nhất nhỏ hơn hoặc bằng <math>\frac{L+R}{2}</math>.
# Nếu <math>A_m < T</math>, gán <math>L</math> với <math>m+1</math> và quay lại bước 2.
# Nếu <math>A_m > T</math>, gán <math>R</math> với <math>m-1</math> và quay lại bước 2.
# Khi <math>A_m = T</math>, quá trình tìm kiếm hoàn tất; trả về <math>m</math>.

Quy trình lặp này dùng hai biến <math>L</math> và <math>R</math> để lưu giới hạn tìm kiếm. Quy trình này có thể diễn giải bằng [[mã giả]] như dưới đây, trong đó tên các biến và kiểu giữ nguyên so với như trên, <code>floor</code> là hàm floor, và <code>không_thành_công</code> là một giá trị cụ thể thông báo tìm kiếm thất bại.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}

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

Ngoài ra, thuật toán có thể lấy giá trị [[Phần nguyên|ceiling]] của <math>\frac{L+R}{2}</math>. Điều này có thể thay đổi kết quả nếu giá trị cần tìm xuất hiện nhiều hơn một lần trong mảng.

==== Cách làm khác ====
Trong quy trình trên, thuật toán kiểm tra phần tử ở giữa (<math>m</math>) có bằng giá trị cần tìm (<math>T</math>) không ở mỗi phép lặp. Một số cách làm bỏ qua bước này ở mỗi phép lặp. Khi đó thuật toán chỉ kiểm tra điều này khi chỉ còn một phần tử còn lại (khi <math>L=R</math>). Nhờ đó mà vòng lặp so sánh được thực hiện nhanh hơn do mỗi phép lặp đã loại bỏ được một bước so sánh. Tuy nhiên, với cách làm này thì số phép lặp trung bình tăng lên.<ref name="Bottenbruch1962">{{chú thích tạp chí|last1=Bottenbruch|first1=Hermann|title=Structure and use of ALGOL 60|journal=[[Journal of the ACM]] |date=ngày 1 tháng 4 năm 1962|volume=9|issue=2|pages=161–221 |issn=0004-5411|doi=10.1145/321119.321120 }} Procedure is described at p. 214 (§43), titled "Program for Binary Search".</ref>

[[Hermann Bottenbruch]] cho xuất bản cách áp dụng đầu tiên bỏ qua bước kiểm tra này vào năm 1962.<ref name="Bottenbruch1962" />{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "History and bibliography"}}

# Gán <math>L</math> với giá trị <math>0</math> và <math>R</math> với giá trị <math>n-1</math>.
# Khi <math>L \neq R</math>,
## Gán <math>m</math> (vị trí của phần tử đứng giữa) với giá trị [[Phần nguyên|ceiling]] của <math>\frac{L+R}{2}</math>, tức là số nguyên nhỏ nhất lớn hơn hoặc bằng <math>\frac{L+R}{2}</math>.
## Nếu <math>A_m > T</math>, gán <math>R</math> với <math>m-1</math>.
## Trường hợp còn lại, <math>A_m \leq T</math>; gán <math>L</math> với <math>m</math>.
# Khi <math>L=R</math>, quá trình tìm kiếm hoàn tất. Nếu <math>A_L=T</math>, trả về <math>L</math>. Nếu không, tìm kiếm thất bại.

Với <code>ceil</code> là hàm ceiling, mã giả cho phiên bản này như sau:

 '''function''' binary_search_alternative(A, n, T) '''is'''
     L:= 0
     R:= n &minus; 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 trên có thể trả về bất cứ chỉ số nào có giá trị phần tử bằng giá trị cần tìm, kể cả khi trong mảng có các phần tử xuất hiện lặp lại. Ví dụ, với mảng <math>[1,2,3,4,4,5,6,7]</math> và giá trị cần tìm là <math>4</math>, thuật toán có thể trả về một trong hai kết quả đúng là phần tử thứ 4 (chỉ số là 3) hoặc thứ 5 (chỉ số là 4). Quy trình chuẩn trong trường hợp này sẽ trả về phần tử thứ 4 (chỉ số 3). Thuật toán này không phải lúc nào cũng trả về vị trí đầu tiên xuất hiện giá trị cần tìm (ví dụ với mảng <math>[1,2,4,4,4,5,6,7]</math>, kết quả trả về vẫn là phần tử thứ 4). Tuy nhiên, có một số trường hợp cần phải tìm phần tử nằm xa nhất về phía bên trái hoặc bên phải mang giá trị cần tìm khi giá trị này xuất hiện lặp lại trong mảng. Trong ví dụ trên, phần tử thứ 4 là phần tử đứng xa nhất về bên trái mang giá trị 4, trong khi phần tử thứ 5 là phần từ đứng xa nhất về bên phải mang giá trị 4. Cách làm thứ hai ở trên sẽ luôn trả về chỉ số của phần tử đứng xa nhất về bên phải nếu tồn tại các phần tử lặp lại.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "History and bibliography"}}

==== Quy trình tìm phần tử xa nhất về bên trái ====
Để tìm phần tử xa nhất về bên trái, ta có thể dùng quy trình sau:{{Sfn|Kasahara|Morishita|2006|pp=8–9}}

# Gán <math>L</math> với giá trị <math>0</math> và <math>R</math> với <math>n</math>.
# Khi <math>L < R</math>,
# Gán <math>m</math> (vị trí của phần tử đứng giữa) với giá trị [[Phần nguyên|floor]] của <math>\frac{L+R}{2}</math>, tức là số nguyên lớn nhất nhỏ hơn hoặc bằng <math>\frac{L+R}{2}</math>.
## Nếu <math>A_m < T</math>, gán <math>L</math> với <math>m+1</math>.
## Trường hợp còn lại, <math>A_m \geq T</math>; gán ''<math>R</math>'' với <math>m</math>.
# Trả về <math>L</math>.

Nếu <math>L < n</math> và <math>A_L = T</math> thì <math>A_L</math> là phần tử đứng xa nhất về bên trái có giá trị bằng <math>T</math>. Kể cả khi <math>T</math> không nằm trong mảng, <math>L</math> là [[#So khớp xấp xỉ|hạng]] của <math>T</math> trong mảng, hay số phần tử trong mảng nhỏ hơn <math>T</math>.

Với <code>floor</code> là hàm floor, mã giả cho phiên bản này như sau:

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

==== Quy trình tìm phần tử xa nhất về bên phải ====

Để tìm phần tử xa nhất về bên phải, ta có thể dùng quy trình sau:{{Sfn|Kasahara|Morishita|2006|pp=8–9}}

# Gán <math>L</math> với giá trị <math>0</math> và <math>R</math> với <math>n</math>.
# Khi <math>L < R</math>,
# Gán <math>m</math> (vị trí của phần tử đứng giữa) với giá trị [[Phần nguyên|floor]] của <math>\frac{L+R}{2}</math>, tức là số nguyên lớn nhất nhỏ hơn hoặc bằng <math>\frac{L+R}{2}</math>.
## Nếu <math>A_m > T</math>, gán <math>R</math> với <math>m</math>.
## Trường hợp còn lại, <math>A_m \leq T</math>; gán ''<math>L</math>'' với <math>m+1</math>.
# Trả về <math>R - 1</math>.

Nếu <math>L > 0</math> và <math>A_{L-1}=T</math>, thì <math>A_{L-1}</math> là phần tử đứng xa nhất về phía bên phải có giá trị bằng <math>T</math>. Kể cả khi ''<math>T</math>'' không có trong mảng, <math>n-L</math> sẽ là số phần tử trong mảng lớn hơn ''<math>T</math>''.

Với <code>floor</code> là hàm floor, mã giả cho phiên bản nà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 suất==
[[Tập tin:Binary search example tree.svg|thumb|upright=0.75|Một [[Cây (cấu trúc dữ liệu)|cây]] biểu diễn tìm kiếm nhị phân. Mảng được dùng trong ví dụ này là <math>[20, 30, 40, 50, 80, 90, 100]</math> và giá trị cần tìm là <math>40</math>.]]
[[Tập tin:Binary search complexity.svg|thumb|upright=2|Trường hợp tệ nhất là khi quá trình tìm kiếm phải đi tới bậc sâu nhất của cây, còn trường hợp tốt nhất là khi giá trị cần tìm chính là phần tử đứng giữa.]]

Về mặt số 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 biểu diễn quá trình chạy thuật toán trên cây nhị phân. Nút gốc của cây là phần tử đứng giữa mảng. Phần tử đứng giữa nửa nhỏ hơn là nút con bên trái của nút gốc, và phần tử đứng giữa nửa lớn hơn là nút con bên phải của nút gốc. Phần còn lại của cây cũng được dựng như vậy. Bắt đầu từ nút gốc, tùy theo giá trị cần tìm nhỏ hơn hay lớn hơn nút đang xét mà thuật toán sẽ duyệt theo cây con bên trái hay bên phải.<ref name="FloresMadpis1971" />{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search"}}

Trong trường hợp tệ nhất, thuật toán thực hiện <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> lần lặp so sánh, trong đó <math display="inline">\lfloor \rfloor</math> là ký hiệu của [[Phần nguyên|hàm floor]] cho kết quả là số nguyên lớn nhất nhỏ hơn hoặc bằng giá trị bên trong, và <math display="inline">\log_2</math> là phép [[Logarit|logarit nhị phân]]. Nguyên nhân là do khi gặp phải trường hợp tệ nhất, thuật toán phải đi tới bậc sâu nhất trong cây, và số bậc trong cây luôn bằng <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> với bất cứ phép tìm kiếm nhị phân nào.

Trường hợp tệ nhất còn có thể xảy ra khi giá trị cần tìm không có trong mảng. Nếu <math display="inline">n</math> ở dạng <math display="inline">2^\alpha - 1</math> thì trường hợp này luôn xảy ra. Nếu không, thuật toán có thể thực hiện <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math>phép lặp nếu phải đi tới bậc sâu nhất của cây. Tuy nhiên, nếu thuật toán kết thúc ngay ở bậc sâu thứ hai của cây, quá trình tìm kiếm có thể chỉ cần thực hiện <math display="inline">\lfloor \log_2 (n) \rfloor</math> phép lặp, ít hơn trường hợp tệ nhất một phép.{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), "Theorem B"}}

Giả sử mỗi phần tử có xác suất được thực hiện tìm kiếm như nhau, trung bình thuật toán tìm kiếm nhị phân thực hiện <math>\lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n</math> phép lặp khi phần tử cần tìm có mặt trong mảng, hay xấp xỉ bằng <math>\log_2(n) - 1</math>. Khi phần tử cần tìm không có trong mảng, thuật toán thực hiện trung bình <math>\lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)</math> phép lặp, nếu giả sử khoảng giữa và bên ngoài các phần tử đều có xác suất được tìm như nhau.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search"}}

Trong trường hợp tốt nhất, khi giá trị cần tìm nằm ngay giữa mảng, vị trí của nó được trả về ngay sau một phép lặp.{{Sfn|Chang|2003|p=169}}

Về mặt số phép lặp, không có thuật toán tìm kiếm nào chỉ bằng so sánh các phần tử có thể có hiệu suất trung bình hay thậm chí trong trường hợp tệ nhất tốt hơn tìm kiếm nhị phân. Cây so sánh biểu diễn tìm kiếm nhị phân có số bậc ít nhất có thể do mọi bậc phía trên bậc thấp nhất của cây đều được lấp đầy hoàn toàn.{{Efn|Bất cứ thuật toán tìm kiếm nào chỉ dựa trên các phép so sánh có thể được biểu diễn bằng cây so sánh nhị phân. ''Đường đi trong'' (''internal path'') là bất kỳ đường nào đi từ gốc tới một nút có sẵn. Gọi <math>I</math> là ''độ dài đường đi trong'' (''internal path length''), hay tổng độ dài tất cả các đường đi trong của cây. Nếu mỗi phần tử có xác suất được tìm như nhau, trường hợp trung bình là <math>1 + \frac{I}{n}</math>, hoặc đơn giản hơn là một cộng với trung bình toàn bộ độ dài các đường đi trong trong cây. Nguyên nhân là do các đường đi trong biểu diễn các phần tử mà thuật toán tìm kiếm tiến hành so sánh với giá trị cần tìm. Độ dài của các đường này biểu diễn số phép lặp ''sau'' nút gốc. Làm phép cộng trung bình tổng độ dài các đường này với thêm một phép lặp nữa ở nút gốc sẽ ra trường hợp trung bình. Do đó, để giảm tối đa số phép so sánh trung bình, cần phải giảm độ dài đường đi trong <math>I</math>. Thực chất cây biểu diễn tìm kiếm nhị phân đã giảm tối đa độ dài đường đi trong. {{Harvnb|Knuth|1998}} chứng minh được rằng độ dài ''đường đi ngoài'' (''external path'' - the path length over all nodes where both children are present for each already-existing node) được giảm tối đa khi các nút ngoài (các nút không có nút con) nằm trong hai bậc liên tiếp của cây. Điều này cũng áp dụng với các đường đi trong do độ dài đường đi trong <math>I</math> có liên hệ tuyến tính với độ dài đường đi ngoài <math>E</math>. Với mỗi cây có <math>n</math> nút, <math>I = E - 2n</math>. Khi mỗi cây con có số nút bằng nhau, tương đương với khi mảng được chia thành hai nửa ở mỗi phép lặp, các nút ngoài và các nút cha phía trong của chúng nằm trong vòng hai bậc. Như vậy, thuật toán tìm kiếm nhị phân đã giảm được tối đa số phép so sánh trung bình do cây so sánh của thuật toán này có độ dài đường trong nhỏ nhất.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search"}}}} Nếu không, thuật toán tìm kiếm có thể loại bỏ một vài phần tử trong mỗi phép lặp, làm tăng số phép lặp cần thực hiện trong trường hợp trung bình và tệ nhất. Các thuật toán tìm kiếm khác dùng cách so sánh đều bị rơi vào trường hợp này, do mặc dù chúng có thể chạy nhanh hơn với một số giá trị cần tìm nhất định, hiệu suất trung bình trên ''tất cả'' phần tử vẫn kém hơn tìm kiếm nhị phân. Bằng cách chia mảng thành hai nửa, thuật toán tìm kiếm nhị phân đảm bảo được kích thước của hai mảng con giống nhau nhất có thể.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

==== Độ phức tạp không gian ====
Thuật toán tìm kiếm nhị phân cần ba con trỏ để trỏ tới 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 con trỏ tới địa chỉ trong bộ nhớ. Tuy nhiên, thuật toán cần ít nhất <math>\left \lceil \log_2(n) \right \rceil</math> bit để mã hóa một con trỏ tới một phần tử trong mảng có <math>n</math> phần tử.<ref>{{chú thích tạp chí |author=Shannon, Claude E. |authorlink=Claude Shannon |title=A Mathematical Theory of Communication |journal=[[Bell System Technical Journal]] |volume=27 |issue=3 |pages=379–423 |date=July 1948 |doi=10.1002/j.1538-7305.1948.tb01338.x|hdl=11858/00-001M-0000-002C-4314-2 }}</ref> Do đó, độ phức tạp không gian của tìm kiếm nhị phân là <math>O(\log n)</math>. Ngoài ra, thuật toán còn cần <math>O(n)</math> không gian để lưu trữ mảng.

=== Trường hợp trung bình ===
Số phép lặp trung bình được thực hiện bởi thuật toán tùy thuộc vào xác suất mỗi phần tử được thực hiện tìm kiế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. Ta giả sử 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. Nếu tìm kiếm không thành công, ta giả sử các [[Khoảng (toán học)|khoảng]] giữa và ngoài các phần tử có xác suất được tìm giống nhau. 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 mọi phần tử chính xác một lần, chia cho <math>n</math>, số phần tử trong mảng. Trường hợp trung bình khi tìm kiếm không thành công là số phép lặp cần thực hiện để tìm một phần tử trong mọi khoảng chính xác một lần, chia cho <math>n + 1</math> khoảng.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search"}}

==== Tìm kiếm thành công ====
<!-- E stands for "expected" -->
Khi biểu diễn bằng cây nhị phân, một lần tìm kiếm thành công có thể được biểu diễn bằng một đường đi từ gốc tới nút cần tìm, gọi là ''đường đi trong'' (''internal path''). Độ dài của một đường đi là số cạnh (đường nối giữa các nút) mà đường đó đi qua. Số phép lặp mà một lần tìm kiếm thực hiện, với điều kiện độ dài của đường đi tương ứng với lần tìm đó là <math>l</math>, là <math>l + 1</math> tính cả phép lặp ban đầu. ''Độ dài đường đi trong'' (''internal path length'') là tổng độ dài tất cả các đường đi trong. Do chỉ có một đường đi duy nhất từ gốc tới bất cứ nút nào, mỗi đường trong đó biểu diễn cho một phép tìm kiếm phần tử tương ứng. Nếu có <math>n</math> phần tử, và độ dài đường trong là <math>I(n)</math>, thì số phép lặp trung bình cho một lần tìm kiếm thành công là <math>T(n) = 1 + \frac{I(n)}{n}</math>, trong đó đã cộng thêm một bước lặp ở đầu.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search"}}

Do tìm kiếm nhị phân là thuật toán tối ưu cho việc tìm kiếm bằng cách so sánh, bài toán đượ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ây nhị phân có <math>n</math> nút, tức là bằng:{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}}

<math>
I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor
</math>

Ví dụ, với một mảng 7 phần tử, phần tử gốc cần một phép lặp, hai phần tử bên dưới gốc cần hai phép lặp, và bốn phần tử dưới nữa gần ba phép lặp. Trong trường hợp này, độ dài đường đi trong là:{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}}

<math>
\sum_{k=1}^7 \left \lfloor \log_2(k) \right \rfloor = 0 + 2(1) + 4(2) = 2 + 8 = 10
</math>

Số phép lặp trung bình sẽ là <math>1 + \frac{10}{7} = 2 \frac{3}{7}</math> dựa theo công thức với trường hợp trung bình. Tổng <math>I(n)</math> có thể rút gọn thành:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor = (n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2
</math>

Thay <math>I(n)</math> vào phương trình <math>T(n)</math>:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
T(n) = 1 + \frac{(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2}{n} = \lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n
</math>

Với <math>n</math> là một số nguyên, phương trình trên tương đương với phương trình trong trường hợp trung bình cho một lần tìm kiếm thành công như đã chỉ ra ở trên.

==== Tìm kiếm không thành công ====
Ta có thể biểu diễn lần tìm kiếm không thành công bằng cách thêm vào cây các ''nút ngoài'', tạo thành ''cây nhị phân mở rộng''. Nếu một nút trong, hoặc một nút có trong cây, có ít hơn hai nút con, thì ta sẽ thêm vào các nút con bổ sung, gọi là các nút ngoài, để mỗi nút trong đều có hai nút con. By doing so, an unsuccessful search can be represented as a path to an external node, whose parent is the single element that remains during the last iteration. ''Đường đi ngoài'' (''external path'') là đường đi từ gốc đến một nút ngoài. ''Độ dài đường đi ngoài'' (''external path length'') là tổng độ dài tất cả đường đi ngoài unique. Nếu số phần tử là <math>n</math> (<math>n</math> là số nguyên dương), và độ dài đường đi ngoài là <math>E(n)</math>, thì số phép lặp trung bình cho một lần tìm kiếm không thành công là <math>T'(n)=\frac{E(n)}{n+1}</math>, trong đó đã tính một phép lặp lúc đầu. Trong công thức này, ta lấy độ dài đường đi ngoài chia cho <math>n+1</math> chứ không phải <math>n</math> vì có <math>n+1</math> đường đi ngoài biểu diễn cho các khoảng giữa và ngoài các phần tử trong mảng.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

Tương tự, bài toán này có thể đơn giản hóa thành bài toán tính độ dài đường đi ngoài tối thiếu của tất cả cây nhị phân có <math>n</math> nút. 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 <math>2n</math>.{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}} Thay <math>I(n)</math> vào ta có:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
E(n) = I(n) + 2n = \left[(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2\right] + 2n = (n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1}
</math>

Thay <math>E(n)</math> vào công thức tính <math>T'(n)</math>, ta có thể xác định trường hợp trung bình cho những lần tìm kiếm không thành công:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

<math>
T'(n) = \frac{(n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1}}{(n+1)} = \lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)
</math>

==== Hiệu suất của các cách thay thế ====
Mỗi phép lặp trong cách tìm kiếm nhị phân trên thực hiện một hoặc hai lần so sánh để kiểm tra phần tử ở giữa có bằng với giá trị cần tìm không. Giả sử mỗi phần tử có xác suất được tìm bằng nhau, mỗi phép lặp thực hiện trung bình 1,5 lần so sánh. Một cách làm khác của thuật toán sẽ thực hiện kiểm tra phần tử giữa ở cuối mỗi lần tìm kiếm. Theo cách này, trung bình mỗi phép lặp bỏ qua 0,5 lần so sánh, tiết kiệm thời gian hơn một chút trên mỗi phép lặp ở hầu hết các loại máy tính. Tuy nhiên, cách này lại khiến mỗi lần tìm kiếm luôn phải thực hiện số phép lặp tối đa, trung bình mỗi lần tìm cộng thêm một phép lặp. Vì vòng lặp so sánh chỉ được thực hiện <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> lần trong trường hợp tệ nhất, việc tăng nhẹ hiệu suất ở mỗi phép lặp không thể bù lại cho phép lặp cần thực hiện thêm khi <math display="inline">n</math> không lớn.{{Efn|{{Harvnb|Knuth|1998}} cho thấy trên mẫu máy tính [[MIX]] của ông, được Knuth thiết kế để biểu diễn cho một chiếc máy tính thông thường, rằng thời gian chạy trung bình của cách làm này cho một lần tìm thành công là <math display="inline">17.5 \log_2 n + 17</math> đơn vị thời gian so với <math display="inline">18 \log_2 n - 16</math> đơn vị với tìm kiếm nhị phân thông thường. Độ phức tạp thời gian của cách làm này tăng nhẹ ở tốc độ chậm hơn, nhưng độ phức tạp ban đầu lớn hơn. {{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Exercise 23"}}}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 23"}}<ref>{{chú thích tạp chí|last1=Rolfe|first1=Timothy J.|title=Analytic derivation of comparisons in binary search|journal=ACM SIGNUM Newsletter|date=1997|volume=32|issue=4|pages=15–19|doi=10.1145/289251.289255}}</ref>

=== Thời gian chạy và mức sử dụng cache ===
Trong quá trình phân tích hiệu suất của thuật toán, một vấn đề khác cần lưu ý là thời gian cần để so sánh hai phần tử. Với các số nguyên và chuỗi ký tự, khoảng thời gian này tăng tuyến tính do độ dài mã hóa (thường là số [[bit]]) của các phần tử tăng theo. Ví dụ, một cặp số nguyên dương 64 bit sẽ cần phải so sánh số bit gấp đôi so với một cặp số nguyên dương 32 bit. Trường hợp tệ nhất được đạt đến khi hai số nguyên bằng nhau. Điều này có thể đáng lưu tâm khi độ dài mã hóa của các phần tử ở mức lớn, ví dụ như khi so sánh các số thuộc kiểu nguyên lớn hơn hay so sánh các chuỗi ký tự dài, khiến cho việc so sánh rất tốn thời gian. Hơn nữa, so với các số nguyên hoặc chuỗi ký tự ngắn thì so sánh các giá trị [[Số thực dấu phẩy động|dấu phẩy động]] (cách biểu diễn số thông dụng nhất của [[số thực]]) thường còn tốn thời gian hơn..

Trên hầu hết các kiểu [[kiến trúc máy tính]], [[CPU|bộ vi xử lý]] có bộ nhớ [[Cache (tin học)|cache]] riêng tách biệt khỏi [[RAM]]. Do nằm ngay trong bộ xử lý, bộ nhớ cache có thể truy cập nhanh hơn nhưng thường chỉ chứa được ít dữ liệu hơn RAM. Do đó, hầu hết các bộ xử lý lưu địa chỉ những vùng bộ nhớ đã được truy cập gần đây và cả những vùng bộ nhớ xung quanh chúng. Ví dụ, khi truy cập vào một phần tử trong mảng, phần tử này, cùng với cả những phần tử được lưu gần đó, có thể được lưu vào trong RAM để sau đó có thể truy cập nhanh hơn được vào các phần tử khác liền kề (tính địa phương trong truy xuất - ''locality of reference''). Với một mảng đã sắp xếp, quá trình tìm kiếm nhị phân có thể phải nhảy sang các vùng bộ nhớ nằm xa nếu mảng có kích thước lớn, không giống như 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ự lần lượt. Điều này làm thời gian chạy của thuật toán tăng lên đôi chút với các mảng lớn trên hầu hết các hệ thống.<ref>{{chú thích tạp chí|last1=Khuong|first1=Paul-Virak|last2=Morin|first2=Pat|author2-link= Pat Morin |title=Array Layouts for Comparison-Based Searching|journal=Journal of Experimental Algorithmics|volume=22|at=Article 1.3|doi=10.1145/289251.289255}}</ref>

== Tìm kiếm nhị phân với các hệ thống khác ==
Áp dụng tìm kiếm nhị phân với các mảng đã được sắp xếp là một giải pháp rất không hiệu quả khi xen giữa các phép chèn và xóa còn là các phép truy hồi, mỗi thao tác đó phải mất <math display="inline">O(n)</math> thời gian để thực hiện. Ngoài ra, yêu cầu phải sắp xếp trước các mảng có thể làm phức tạp việc sử dụng bộ nhớ, đặc biệt là khi các phần tử thường được chèn vào trong mảng.{{Sfn|Knuth|1997|loc=§2.2.2 ("Sequential Allocation")}} 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 nhiều. Tìm kiếm nhị phân có thể được dùng để thực hiện so khớp chính xác và thao tác [[Tập hợp (cấu trúc dữ liệu trừu tượng)|quan hệ tập hợp]] (xác định giá trị cần tìm có phải là một tập hợp nhiều giá trị không). Hai bài toán này cũng có thể được 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 chỉ thực hiện trong <math display="inline">O(\log n)</math> thời gian bất kể kiểu hay cấu trúc của các giá trị.<ref name="pred">{{chú thích tạp chí|last1=Beame|first1=Paul|last2=Fich|first2=Faith E.|authorlink2=Faith Ellen|title=Optimal bounds for the predecessor problem and related problems|journal=[[Journal of Computer and System Sciences]]|date=2001|volume=65|issue=1|pages=38–72|doi=10.1006/jcss.2002.1822}}</ref> Ngoài ra còn có 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ả trên mảng đã được sắp xếp.{{sfn|Sedgewick|Wayne|2011|loc=§3.1, subsection "Rank and selection"}}

=== Tìm kiếm tuyến tính ===
[[Tìm kiếm tuyến tính]] là một thuật toán tìm kiếm đơn giản: nó kiểm tra mọi bản ghi cho tới khi tìm thấy giá trị cần tìm. Tìm kiếm tuyến tính có thể được thực hiện trên [[danh sách liên kết]], cho phép các thao tác chèn và xóa nhanh hơn so với mảng. Tìm kiếm nhị phân nhanh hơn tìm kiếm tuyến tính trên các mảng đã được sắp xếp trừ khi mảng có kích thước nhỏ, mặc dù trước khi tìm kiếm cần phải thực hiện sắp xếp lại mảng trước.{{Efn|{{Harvnb|Knuth|1998}} đã thực hiện phân tích hiệu suất thời gian của cả hai thuật toán tìm kiếm này. Trên chiếc máy tính [[MIX]] của Knuth, được ông thiết kế để biểu diễn cho một chiếc máy tính thông thường, tìm kiếm nhị phân trung bình mất <math display="inline">18 \log n - 16</math> đơn vị thời gian cho một lần tìm kiếm thành công, trong khi tìm kiếm tuyến tính khi có một [[sentinel node]] ở cuối danh sách mất <math display="inline">1.75n + 8.5 - \frac{n \text{ mod } 2}{4n}</math> đơn vị. Tìm kiếm tuyến tính có độ phức tạp ban đầu thấp hơn do nó chỉ yêu cầu các tính toán tối thiểu, nhưng sau đó nhanh chóng vượt qua tìm kiếm nhị phân về độ phức tạp. Trên máy tính MIX, binary search only outperforms linear search with a sentinel if <math display="inline">n > 44</math>.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search"}}{{Sfn|Knuth|1998|loc=Answers to Exercises  (§6.2.1) cho "Exercise 5"}}}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table")}} Tất cả các [[thuật toán sắp xếp]] dựa trên thao tác so sánh các phần tử, như [[sắp xếp nhanh]] và [[sắp xếp trộn]], cần ít nhất <math display="inline">O(n \log n)</math> phép so sánh trong trường hợp tệ nhất.{{Sfn|Knuth|1998|loc=§5.3.1 ("Minimum-Comparison sorting")}} Khác với tìm kiếm tuyến tính, tìm kiếm nhị phân có thể được ứng dụng để tìm so khớp 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 có thể được thực hiện hiệu quả chỉ khi mảng đã được sắp xếp.{{Sfn|Sedgewick|Wayne|2011|loc=§3.2 ("Ordered symbol tables")}}

=== Cây ===
[[Tập tin:Binary search tree search 4.svg|thumb|upright=1.0|Phép tìm kiếm trên [[cây tìm kiếm nhị phân]] sử dụng một thuật toán tương tự tìm kiếm nhị phân.]]

[[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]] hoạt động 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 biểu diễn theo thứ tự đã được sắp xếp, và mỗi bản ghi có thể được tìm bằng một thuật toán tương tự tìm kiếm nhị phân, thực hiện trung bình theo thời gian logarit. Các phép chèn và xóa cũng cần trung bình thời gian logarit trong cây tìm kiếm nhị phân. Chúng có thể được thực hiện nhanh hơn so với các thao tác chèn và xóa theo thời gian tuyến tính trên các mảng đã được sắp xếp, đồng thời các thao tác có thể thực hiện trên mảng đã được sắp xếp cũng có thể được thực hiện trên cây nhị phân, bao gồm cả các phép truy vấn khoảng và truy vấn xấp xỉ.<ref name="pred" />{{Sfn|Sedgewick|Wayne|2011|loc=§3.2 ("Binary Search Trees"), subsection "Order-based methods and deletion"}}

Tuy nhiên, tìm kiếm nhị phân thường hiệu quả hơn trong việc tìm kiếm, do các cây nhị phân hầu như đều không cân bằng tuyệt đối, khiến hiệu suất kém hơn đôi chút so với tìm kiếm nhị phân. Điều này thậm chí vẫn áp dụng với các [[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 có số bậc nhỏ nhất có thể. Ngoại trừ các cây tìm kiếm nhị phân đã cân bằng, việc có quá ít số nút trong có đúng hai nút con có thể khiến cây bị mất cân bằng rất nhiều, khiến thời gian tìm kiếm ở trường hợp trung bình và tệ nhất có thể tiến tới ngưỡng <math display="inline">n</math> phép so sánh.{{Efn|Đưa các giá trị vào theo thứ tự được sắp xếp hay theo quy luật khóa thấp nhất-cao nhất luân phiên sẽ tạo ra một cây tìm kiếm nhị phân có thời gian tìm kiếm tối đa ở trung bình và tệ nhất.{{Sfn|Knuth|1998|loc=§6.2.2 ("Binary tree searching"), phân mục "But what about the worst case?"}}}} Cây tìm kiếm nhị phân cần nhiều không gian hơn so với mảng đã được sắp xếp.{{Sfn|Sedgewick|Wayne|2011|loc=§3.5 ("Applications"), "Which symbol-table implementation should I use?"}}

Cây tìm kiếm nhị phân hữu ích nhất cho việc tìm kiềm nhanh trong các ổ cứng ngoài, bởi cây tìm kiếm nhị phân có thể được dựng hiệu quả trong các hệ thống tập tin. Cấu trúc [[B-cây]] tổng quát hóa phương pháp tổ chức cây này. B-cây thường được dùng để tổ chức các ổ lưu trữ dài hạn như [[cơ sở dữ liệu]] và [[hệ thống tập tin]].{{Sfn|Knuth|1998|loc=§5.4.9 ("Disks and Drums")}}{{Sfn|Knuth|1998|loc=§6.2.4 ("Multiway trees")}}

=== Băm ===
Với các [[mảng kết hợp]], [[bảng băm]], một cấu trúc dữ liệu dùng [[hàm băm]] để ánh xạ các khóa thành các [[bản ghi]], thường hoạt động nhanh hơn tìm kiếm nhị phân trên một mảng chứa các bản ghi đã được sắp xếp.{{Sfn|Knuth|1998|loc=§6.4 ("Hashing")}} Hầu hết các cách triển khai bảng băm chỉ yêu cầu trung bình thời gian hằng số [[Phân tích khấu hao|khấu hao]].{{efn|Một số cách triển khai bảng băm có thể thực hiện tìm kiếm với thời gian hằng số đảm bảo.{{Sfn|Knuth|1998|loc=§6.4 ("Hashing"), phân mục "History"}}}}<ref>{{chú thích tạp chí|last1=Dietzfelbinger|first1=Martin|last2=Karlin|first2=Anna|last3=Mehlhorn|first3=Kurt|last4=Meyer auf der Heide|first4=Friedhelm|last5=Rohnert|first5=Hans|last6=Tarjan|first6=Robert E.|authorlink2=Anna Karlin|authorlink3=Kurt Mehlhorn|authorlink6=Robert Tarjan|title=Dynamic perfect hashing: upper and lower bounds|journal=[[SIAM Journal on Computing]]|date=August 1994|volume=23|issue=4|pages=738–761|doi=10.1137/S0097539791194094}}</ref> Tuy nhiên, việc băm có thể không hữu ích khi thực hiện các bài toán so khớp xấp xỉ, ví dụ như tính khóa nhỏ nhất tiếp theo, khóa lớn nhất tiếp theo và khóa gần nhất, do khi tìm kiếm thất bại, thông tin duy nhất được đưa ra là giá trị cần tìm không có trong bất cứ bản ghi nào.<ref>{{chú thích web|last1=Morin|first1=Pat|title=Hash tables|url=http://cglab.ca/~morin/teaching/5408/notes/hashing.pdf|access-date =ngày 28 tháng 3 năm 2016|page=1}}</ref> Tìm kiếm nhị phân là cách làm lý tưởng đối với những bài toán như vậy, khi chỉ thực hiện với thời gian chạy logarit. Tìm kiếm nhị phân 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ể được thực hiện hiệu quả trên các mảng đã được sắp xếp, nhưng không thể trên bảng băm.<ref name="pred" />

===Các thuật toán quan hệ tập hợp===
Một vấn đề liên quan tới tìm kiếm là [[Tập hợp (cấu trúc dữ liệu trừu tượng)|quan hệ tập hợp]]. Bất cứ thuật toán nào thực hiện tra cứu, như tìm kiếm nhị phân, cũng có thể dùng cho quan hệ tập hợp. Một số thuật toán khác được thiết kế phù hợp hơn với quan hệ tập hợp. [[Mảng bit]] là cách làm đơn giản nhất, thường được dùng khi số khóa bị giới hạn. Cấu trúc này lưu trữ các [[bit]] một cách nhỏ gọn, mỗi bit biểu diễn cho một khóa trong khoảng cho trước. Mảng bit hoạt động rất nhanh, chỉ trong thời gian <math display="inline">O(1)</math>.{{Sfn|Knuth|2011|loc=§7.1.3 ("Bitwise Tricks and Techniques")}}  Một loại [[mảng Judy]] là Judy1 có thể xử lý hiệu quả các khóa 64-bit.<ref name="judyarray">{{Citation|last1=Silverstein|first1=Alan|title=Judy IV shop manual|publisher=[[Hewlett-Packard]]|url=http://judy.sourceforge.net/doc/shop_interm.pdf|pp=80–81}}</ref>

Nếu chỉ cần kết quả xấp xỉ, ta có thể sử dụng [[bộ lọc Bloom]], một cấu trúc dữ liệu xác suất khác dựa trên hàm băm, lưu trữ một tập hợp các khóa bằng cách sử dụng một mảng bit và nhiều hàm băm để mã hóa các khóa. Các bộ lọc Bloom chiếm ít không gian hơn nhiều so với các mảng bit trong hầu hết mọi trường hợp và không hoạt động chậm hơn là bao: với <math display="inline">k</math> hàm băm, các phép truy vấn kiểm tra phần tử chỉ cần thời gian <math display="inline">O(k)</math>. Tuy nhiên, sử dụng bộ lọc Bloom có thể đem kết quả [[Lỗi loại I và loại II|dương tính giả]].{{Efn|This is because simply setting all of the bits which the hash functions point to for a specific key can affect queries for other keys which have a common hash location for one or more of the functions.<ref name="cuckoofilter">{{cite conference|last1=Fan|first1=Bin|last2=Andersen|first2=Dave G.|last3=Kaminsky|first3=Michael|last4=Mitzenmacher|first4=Michael D.|title=Cuckoo filter: practically better than Bloom|conference=Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies|date=2014|pages=75–88|doi=10.1145/2674005.2674994}}</ref>}}{{Efn|Có một số bản cải thiện của bộ lọc Bloom giúp cải thiện độ phức tạp hoặc cho phép thao tác xóa; ví dụ, bộ lọc cuckoo sử dụng cách băm cuckoo nhằm những mục đích trên.<ref name="cuckoofilter" />}}<ref>{{chú thích tạp chí|last1=Bloom|first1=Burton H.|title=Space/time trade-offs in hash coding with allowable errors|journal=[[Communications of the ACM]]|date=1970|volume=13|issue=7|pages=422–426|doi=10.1145/362686.362692|df=dmy-all|bibcode=1985CACM...28...22S|citeseerx=10.1.1.641.9096}}</ref>

=== Các cấu trúc dữ liệu khác ===
Còn có các cấu trúc dữ liệu khác có thể cải thiện tìm kiếm nhị phân trong một số trường hợp với cả mục đích tìm kiếm lẫn các thao tác khác có thể được thực hiện trên các mảng đã được sắp xếp. Ví dụ, các phép tìm kiếm, so khớp xấp xỉ và các thao tác khác trên mảng đã được sắp xếp có thể được thực hiện hiệu quả hơn tìm kiếm nhị phân nếu áp dụng trên các cấu trúc dữ liệu chuyên biệt như cây van Emde Boas, [[fusion tree]]s, [[trie]] và [[mảng bit]]. Các cấu trúc dữ liệu chuyên biệt này thường chỉ nhanh hơn vì chúng sử dụng các tính chất của những khóa có điều kiện nhất định (thông thường những khóa này là các số nguyên nhỏ), và do đó thời gian chạy hoặc không gian cần sử dụng có thể lớn nếu không đáp ứng được các điều kiện ấy.<ref name="pred" /> Với điều kiện có thể sắp xếp được các khóa, các thao tác này luôn luôn có thể được thực hiện hiệu quả trên một mảng đã được sắp xếp trước, không phụ thuộc vào các khóa. Một số cấu trúc như mảng Judy sử dụng kết hợp nhiều phương pháp nhằm đơn giản hóa điều kiện trên, nhưng vẫn giữ được sự hiệu quả và khả năng thực hiện so khớp xấp xỉ.<ref name="judyarray" />

==Biến thể==

===Tìm kiếm nhị phân đồng nhất===
{{main|Tìm kiếm nhị phân đồng nhất}}
[[Tập tin:Uniform binary search.svg|thumb|upright=1.0|[[Tìm kiếm nhị phân đồng nhất]] lưu khoảng cách giữa phần tử giữa hiện tại và hai phần tử giữa ở các vòng lặp tiếp theo thay vì sử dụng các giới hạn cụ thể.]]
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 lưu khoảng cách về chỉ số của phần tử đứng giữa ở vòng lặp này với vòng lặp tiếp theo. Thuật toán sẽ lập một bảng dò tìm (''[[lookup table]]'') chứa các khoảng cách này. Ví dụ, nếu mảng cần tìm là {{math|[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]}}, phần tử giữa (<math>m</math>) sẽ là {{math|6}}. Trong trường hợp này, phần tử giữa của mảng con bên trái ({{math|[1, 2, 3, 4, 5]}}) là {{math|3}} và phần tử giữa của mảng con bên phải ({{math|[7, 8, 9, 10, 11]}}) là {{math|9}}. Thuật toán sẽ lưu giá trị {{math|3}}, chính là khoảng cách từ hai chỉ số con trên tới phần tử giữa ban đầu là {{math|6}}.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "An important variation"}} Để giảm không gian tìm kiếm, thuật toán sẽ cộng thêm hoặc trừ bớt lượng thay đổi này so với chỉ số của phần tử đứng giữa. Tìm kiếm nhị phân đồng nhất có thể chạy nhanh hơn trên các hệ thống không có khả năng tính được điểm giữa một cách hiệu quả, như trên các [[máy tính thập phân]].{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm U"}}

===Tìm kiếm mũ{{anchor|One-sided search}}===
{{main|Tìm kiếm mũ}}
[[Tập tin:Exponential search.svg|thumb|upright=1.5|Minh họa thuật toán [[tìm kiếm mũ]] tìm giới hạn trên để thực hiện tìm kiếm nhị phân]]
Tìm kiếm mũ là thuật toán mở rộng của tìm kiếm nhị phân với các danh sách không có giới hạn. Thuật toán bắt đầu bằng việc tìm phần tử đầu tiên có chỉ số là một [[lũy thừa]] của hai và đồng thời có giá trị lớn hơn giá trị cần tìm. Sau đó, chỉ số này sẽ được đặt làm giới hạn trên, và quá trình tìm kiếm tiếp tục dưới dạng tìm kiếm nhị phân. Một lần tìm kiếm thực hiện <math display="inline">\lfloor \log_2 x + 1\rfloor</math> phép lặp trước khi bắt đầu tìm kiếm nhị phân, cộng thêm nhiều nhất <math display="inline">\lfloor \log_2 x \rfloor</math> phép lặp khi thực hiện tìm kiếm nhị phân, trong đó <math display="inline">x</math> là vị trí của giá trị cần tìm. Tìm kiếm mũ cũng hoạt động với các danh sách có giới hạn, nhưng chỉ hiệu quả hơn tìm kiếm nhị phân khi giá trị cần tìm nằm gần đầu mảng.{{sfn|Moffat|Turpin|2002|p=33}}

===Tìm kiếm nội suy===
{{main|Tìm kiếm nội suy}}
[[Tập tin:Interpolation search.svg|thumb|upright=1.5|Minh họa thuật toán [[tìm kiếm nội suy]] sử dụng nội suy tuyến tính. Trong trường hợp này, việc tìm kiếm không cần thực hiện nữa do vị trí ước lượng của giá trị cần tìm trong mảng đã chính xác. Các cách áp dụng khác có thể dùng một hàm khác để ước lượng vị trí của giá trị cần tìm.]]
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 phần tử lớn nhất, nhỏ nhất và kích thước của mảng. Thuật toán này hoạt động dựa trên thực tế rằng trong nhiều trường hợp, vị trí đứng giữa có thể không phải vị trí ước lượng tốt nhất. Ví dụ, nếu giá trị cần tìm nằm gần với phần tử lớn nhất trong mảng, nhiều khả năng nó sẽ nằm ở cuối mảng.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Interpolation search"}}

Một loại hàm nội suy thường được sử dụng là [[nội suy tuyến tính]]. Nếu <math>A</math> là mảng cần tìm, <math>L, R</math> lần lượt là các giới hạn dưới và trên, và <math>T</math> là giá trị cần tìm, thì giá trị cần tìm được ước lượng nằm ở khoảng <math>(T - A_L) / (A_R - A_L)</math> khoảng cách giữa <math>L</math> và <math>R</math>. Khi áp dụng nội suy tuyến tính, and the distribution of the array elements is uniform or near uniform, tìm kiếm nội suy thực hiện <math display="inline">O(\log \log n)</math> phép so sánh.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Interpolation search"}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Exercise 22"}}<ref>{{chú thích tạp chí|last1=Perl|first1=Yehoshua|last2=Itai|first2=Alon|last3=Avni|first3=Haim|title=Interpolation search—a log log ''n'' search|journal=[[Communications of the ACM]]|date=1978|volume=21|issue=7|pages=550–553|doi=10.1145/359545.359557|bibcode=1985CACM...28...22S}}</ref>

Trong thực tế, tìm kiếm nội suy chạy chậm hơn tìm kiếm nhị phân đối với các mảng nhỏ, do tìm kiếm nội suy cần 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 chỉ bù đắp được cho phần tính toán cộng thêm khi mảng có kích thước lớn.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Interpolation search"}}

=== Đổ xuống một phần ===
{{Main|Đổ xuống một phần}}
[[Tập tin:Fractional cascading.svg|thumb|upright=2.5|Trong đổ xuống một phần, mỗi mảng chứa các con trỏ trỏ tới mỗi phần tử thứ hai của một mảng khác, do đó chỉ cần thực hiện một lần tìm kiếm nhị phân để tìm trong tất cả các mảng.]]
Đổ xuống một phần là kỹ thuật nhằm làm 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 từng mảng tách riêng nhau ta phải cần <math display="inline">O(k \log n)</math> thời gian, trong đó <math display="inline">k</math> là số mảng. Phương pháp đổ xuống một phần làm giảm con số này xuống còn <math display="inline">O(k + \log n)</math> bằng cách lưu các thông tin cụ thể ở mỗi mảng về mỗi phần tử và vị trí của chúng ở các mảng khác.<ref name="ChazelleLiu2001">{{cite conference|last1=Chazelle|first1=Bernard|last2=Liu|first2=Ding|authorlink1=Bernard Chazelle|title=Lower bounds for intersection searching and fractional cascading in higher dimension|conference=33rd [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]]|pages=322–329|date=ngày 6 tháng 7 năm 2001|doi=10.1145/380752.380818|url=https://dl.acm.org/citation.cfm?doid=380752.380818 |access-date =ngày 30 tháng 6 năm 2018 |publisher=ACM|isbn=978-1-58113-349-3}}</ref><ref name="ChazelleLiu2004">{{chú thích tạp chí|last1=Chazelle|first1=Bernard|last2=Liu|first2=Ding|authorlink1=Bernard Chazelle|title=Lower bounds for intersection searching and fractional cascading in higher dimension|journal=Journal of Computer and System Sciences|date=ngày 1 tháng 3 năm 2004 |volume=68|issue=2|pages=269–284 |language=en |issn=0022-0000|doi=10.1016/j.jcss.2003.07.003|citeseerx=10.1.1.298.7772|url=http://www.cs.princeton.edu/~chazelle/pubs/FClowerbounds.pdf|access-date =ngày 30 tháng 6 năm 2018}}</ref>

Phương pháp đổ xuống một phần ban đầu được phát triển để giải quyết các bài toán trong [[hình học tính toán]]. Phương pháp này đã được áp dụng trong nhiều lĩnh vực khác, như [[khai phá dữ liệu]] và định tuyến [[Internet Protocol|giao thức Internet]].<ref name="ChazelleLiu2001" />

=== Tổng quát với đồ thị ===
Tìm kiếm nhị phân đã được tổng quát để hoạt động với một số loại đồ thị, trong đó giá trị cần tìm được lưu trong một đỉnh thay vì phần tử của một mảng. Cây tìm kiếm nhị phân chính là một trong số những cách tổng quát đó&mdash;khi một đỉnh (nút) trong cây được truy vấn, thuật toán sẽ xác định hoặc là đỉnh đó chính là giá trị cần tìm, hoặc đi tìm cây con có giá trị cần tìm. Quá trình này còn có thể khái quát hơn nữa như sau: cho một đồ thị vô hướng, trọng số dương và một đỉnh cần tìm, khi truy vấn một đỉnh, thuật toán sẽ xác định hoặc đỉnh đó bằng đỉnh cần tìm, hoặc tìm được cạnh kề nằm trong đường đi ngắn nhất từ đỉnh đang xét đến đỉnh cần tìm. Thuật toán tìm kiếm nhị phân tiêu chuẩn là trường hợp đặc biệt khi đồ thị chỉ là một đường đi. Tương tự, các cây tìm kiếm nhị phân là trường hợp mà các cạnh thuộc cây con bên trái hoặc bên phải được tìm ra nếu đỉnh được truy vấn không bằng đỉnh cần tìm. Với mọi đồ thị vô hướng có trọng số dương, luôn tồn tại một thuật toán có thể tìm ra một đỉnh cho trước trong <math>O(\log n)</math> phép truy vấn ở trường hợp tệ nhất.<ref>{{cite conference|last1=Emamjomeh-Zadeh|first1=Ehsan|last2=Kempe|first2=David|last3=Singhal|first3=Vikrant|title=Deterministic and probabilistic binary search in graphs|date=2016|pages=519–532|conference=48th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]]|arxiv=1503.00805|doi=10.1145/2897518.2897656}}</ref>

=== Tìm kiếm nhị phân nhiễu ===
[[Tập tin:Noisy binary search.svg|thumb|upright=1.5|Trong tìm kiếm nhị phân nhiễu, chắc chắn tồn tại xác suất phép so sánh cho kết quả sai.]]
Các thuật toán tìm kiếm nhị phân nhiễu (''noisy binary search'') có thể giải quyết các trường hợp mà thuật toán không thể so sánh chính xác các phần tử trong mảng. Ở mỗi cặp phần tử đều tồn tại một xác suất nhất định rằng thuật toán thực hiện sai phép so sánh. Tìm kiếm nhị phân nhiễu có thể tìm 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 kiểm soát độ chính xác của kết quả. Mỗi lần tìm kiếm nhị phân nhiễu phải thực hiện trung bình ít nhất <math>(1 - \tau)\frac{\log_2 (n)}{H(p)} - \frac{10}{H(p)}</math> phép so sánh, trong đó <math>H(p) = -p \log_2 (p) - (1 - p) \log_2 (1 - p)</math><!-- Attribution of LaTeX code: see history of https://en.wikipedia.org/wiki/Binary_entropy_function --> là [[hàm entropy nhị phân]] và <math>\tau</math> là xác suất một lần tìm kiếm cho ra kết quả sai.<ref>{{cite conference |last1=Ben-Or |first1=Michael |last2=Hassidim |first2=Avinatan |title=The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well) |date=2008 |book-title=49th [[Annual IEEE Symposium on Foundations of Computer Science|Symposium on Foundations of Computer Science]] |pages=221–230 |doi=10.1109/FOCS.2008.58 |url=http://www2.lns.mit.edu/~avinatan/research/search-full.pdf |isbn=978-0-7695-3436-7}}</ref><ref name="pelc1989">{{chú thích tạp chí|last1=Pelc|first1=Andrzej|title=Searching with known error probability|url=https://archive.org/details/sim_theoretical-computer-science_1989-02_63_2/page/185|journal=Theoretical Computer Science|date=1989|volume=63|issue=2|pages=185–202|doi=10.1016/0304-3975(89)90077-7}}</ref><ref>{{cite conference|last1=Rivest|first1=Ronald L.|last2=Meyer|first2=Albert R.|last3=Kleitman|first3=Daniel J.|last4=Winklmann|first4=K.|authorlink1=Ronald Rivest|authorlink2=Albert R. Meyer|authorlink3=Daniel Kleitman|title=Coping with errors in binary search procedures|conference=10th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]]|doi=10.1145/800133.804351}}</ref> Bài toán tìm kiếm nhị phân nhiễu có thể được coi là một trường hợp của [[Ulam's game|trò chơi Rényi-Ulam]],<ref>{{chú thích tạp chí|last1=Pelc|first1=Andrzej|title=Searching games with errors—fifty years of coping with liars|journal=Theoretical Computer Science|date=2002|volume=270|issue=1–2|pages=71–109|doi=10.1016/S0304-3975(01)00303-6}}</ref> một biến thể của trò chơi [[Twenty Questions|Hai mươi câu hỏi]] trong đó các câu trả lời có thể sai.<ref>{{Chú thích tạp chí | last1=Rényi | first1=Alfréd | title=On a problem in information theory | language=hu | mr=0143666 | year=1961 | journal=Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei| volume=6 | pages=505–516}}</ref>

=== Tìm kiếm nhị phân lượng tử ===
Các máy tính cổ điển khi thực hiện tìm kiếm nhị phân bị giới hạn số phép lặp ở mức <math display="inline">\lfloor \log_2 n + 1 \rfloor</math> trong trường hợp tệ nhất. Các [[thuật toán lượng tử]] dành cho tìm kiếm nhị phân vẫn chỉ bó buộc trong khoảng <math display="inline">\log_2 n</math> phép truy vấn (biểu diễn cho phép lặp trong trường hợp cổ điển), nhưng có hệ số nhỏ hơn một, do đó làm giảm độ phức tạp thời gian trên các [[máy tính lượng tử]]. Bất cứ thao tác tìm kiếm nhị phân lượng tử ''chính xác'' nào—tức là thao tác luôn cho kết quả đúng—cần ít nhất <math display="inline">\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n</math> phép truy vấn ở trường hợp tệ nhất, trong đó <math display="inline">\ln</math> là hàm [[logarit tự nhiên]].<ref>{{chú thích tạp chí|last1=Høyer|first1=Peter|last2=Neerbek|first2=Jan|last3=Shi|first3=Yaoyun|title=Quantum complexities of ordered searching, sorting, and element distinctness|journal=[[Algorithmica]]|date=2002|volume=34|issue=4|pages=429–448|doi=10.1007/s00453-002-0976-3|arxiv=quant-ph/0102078}}</ref> Có một phương pháp tìm kiếm nhị phân lượng tử chính xác chạy trong <math display="inline">4 \log_{605} n \approx 0.433 \log_2 n</math> phép truy vấn ở trường hợp tệ nhất.<ref name="quantumalgo">{{chú thích tạp chí|last1=Childs|first1=Andrew M.|last2=Landahl|first2=Andrew J.|last3=Parrilo|first3=Pablo A.|title=Quantum algorithms for the ordered search problem via semidefinite programming|journal=Physical Review A|date=2007|volume=75|issue=3|at=032335|doi=10.1103/PhysRevA.75.032335|arxiv=quant-ph/0608161|bibcode=2007PhRvA..75c2335C}}</ref> So với các thuật toán khác, [[thuật toán Grover]] là thuật toán lượng tử tối ưu cho việc tìm kiếm trong một danh sách các phần tử chưa được sắp xếp, với <math>O(\sqrt{n})</math> phép truy vấn.<ref>{{cite conference |last1=Grover |first1=Lov K. | authorlink=Lov Grover | title=A fast quantum mechanical algorithm for database search | conference=28th [[Symposium on Theory of Computing|ACM Symposium on Theory of Computing]] |pages=212–219|date=1996| location=Philadelphia, PA | doi=10.1145/237814.237866| arxiv=quant-ph/9605043}}</ref>

== Lịch sử ==
Ý tưởng về việc sắp xếp một danh sách để tìm kiếm được nhanh hơn đã có từ thời cổ xưa. Ví dụ được biết tới sớm nhất là tấm bảng của Inakibit-Anu từ thời Babylon vào {{circa|200 TCN}}. Tấm bảng này chứa khoảng 500 con số ở [[hệ thập lục phân]] và các [[nghịch đảo phép nhân|số nghịch đảo]] của chúng được sắp xếp theo thứ tự từ điển, khiến việc tìm kiếm dễ dàng hơn. Ngoài ra trên [[Quần đảo Aegean]] còn phát hiện được một vài danh sách những cái tên được sắp xếp theo chữ cái đầu tiên. ''[[Catholicon (1286)|Catholicon]]'', một cuốn từ điển Latin được hoàn thành vào năm 1286 SCN, là tác phẩm đầu tiên mô tả các quy tắc sắp xếp các từ theo thứ tự bảng chữ cái, thay vì chỉ theo vài ký tự đầu tiên.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "History and bibliography"}}

Vào năm 1946, [[John Mauchly]] là người đầu tiên nhắc tới tìm kiếm nhị phân trong ''Moore School Lectures'', một khóa học về máy tính tại Trường Kỹ thuật Điện tử Moore, [[Đại học Pennsylvania]].{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "History and bibliography"}} Năm 1957, [[W. Wesley Peterson|William Wesley Peterson]] xuất bản phương pháp đầu tiên cho giải thuật tìm kiếm nội suy.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "History and bibliography"}}<ref>{{chú thích tạp chí |last1=Peterson |first1=William Wesley |authorlink=W. Wesley Peterson|title=Addressing for random-access storage |url=https://archive.org/details/sim_ibm-journal-of-research-and-development_1957-04_1_2/page/130 |journal=IBM Journal of Research and Development |date=1957 |volume=1 |issue=2 |pages=130–146 |doi=10.1147/rd.12.0130}}</ref> Mọi thuật toán tìm kiếm nhị phân đã được xuất bản chỉ hoạt động với các mảng có độ dài ở dạng <math>2^\alpha - 1</math>{{efn|Tức là các mảng có độ dài 1, 3, 7, 15, 31...<ref>"2<sup>''n''</sup>−1". [[On-Line Encyclopedia of Integer Sequences|OEIS]] [http://oeis.org/A000225 A000225] {{Webarchive|url=https://web.archive.org/web/20160608084228/http://oeis.org/A000225 |date=ngày 8 tháng 6 năm 2016 }}.  Truy cập ngày 7 tháng 5 năm 2016.</ref>}} cho tới năm 1960, khi [[Derrick Henry Lehmer]] cho xuất bản một thuật toán tìm kiếm nhị phân có thể hoạt động với mọi mảng.<ref>{{cite conference | title=Teaching combinatorial tricks to a computer | author=Lehmer, Derrick | journal=Proceedings of Symposia in Applied Mathematics | year=1960 | volume=10 | pages=180–181 | doi=10.1090/psapm/010}}</ref> Năm 1962, Hermann Bottenbruch trình bày thuật toán tìm kiếm nhị phân được áp dụng bằng ngôn ngữ [[ALGOL 60]], trong đó [[#Cách làm khác|bước kiểm tra phần tử giữa được đưa xuống cuối]], làm tăng số phép lặp trung bình thêm một, nhưng giảm được một bước so sánh mỗi phép lặp.<ref name="Bottenbruch1962" /> Thuật toán [[#Uniform binary search|uniform binary search]] được phát triển bởi A. K. Chandra tại [[Đại học Stanford]] vào năm 1971.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "History and bibliography"}} 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 đề về tìm kiếm trong [[hình học tính toán]].<ref name="ChazelleLiu2001" /><ref>{{chú thích tạp chí | last1 = Chazelle | first1 = Bernard | authorlink1 = Bernard Chazelle| last2 = Guibas | first2 = Leonidas J. | authorlink2 = Leonidas J. Guibas| title = Fractional cascading: I. A data structuring technique| journal = [[Algorithmica]]| volume = 1 | issue = 1–4 | year = 1986 | pages = 133–162 | doi = 10.1007/BF01840440| url = http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading1.pdf| citeseerx = 10.1.1.117.8349 }}</ref><ref>{{citation| last1 = Chazelle | first1 = Bernard | authorlink1 = Bernard Chazelle| last2 = Guibas | first2 = Leonidas J. | authorlink2 = Leonidas J. Guibas| title = Fractional cascading: II. Applications| journal = [[Algorithmica]]| volume = 1 | issue = 1–4 | year = 1986 | pages = 163–191 | doi = 10.1007/BF01840441| url = http://www.cs.princeton.edu/~chazelle/pubs/FractionalCascading2.pdf}}</ref>

==Thư viện hỗ trợ==
Nhiều [[thư viện chuẩn]] của các ngôn ngữ có các chương trình con thực hiện tìm kiếm nhị phân:
* [[C (ngôn ngữ lập trình)|C]] cung cấp [[chương trình con|hàm]] <code>bsearch()</code> trong [[Thư viện chuẩn C|thư viện chuẩn]], thường được triển khai bằng tìm kiếm nhị phân, mặc dù tiêu chuẩn chính thức không yêu cầu.<ref>{{chú thích web|title=bsearch – binary search a sorted table|url=http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html|website=The Open Group Base Specifications|edition=7 |publisher=[[The Open Group]]|access-date =ngày 28 tháng 3 năm 2016|date=2013|archive-url=https://web.archive.org/web/20160321211605/http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html|archive-date=ngày 21 tháng 3 năm 2016|url-status=live|df=dmy-all}}</ref>
* [[Standard Template Library]] của [[C++]] cung cấp các hàm <code>binary_search()</code>, <code>lower_bound()</code>, <code>upper_bound()</code> và <code>equal_range()</code>.{{Sfn|Stroustrup|2013|p=945}}
* [[COBOL]] cung cấp động từ <code>SEARCH ALL</code> có chức năng thực hiện tìm kiếm nhị phân trên các bảng được sắp xếp trong COBOL.<ref>{{Citation|title=COBOL ANSI-85 programming reference manual|author=Unisys|date=2012|volume=1|pp=598–601|author-link=Unisys}}</ref>
* Gói thư viện chuẩn <code>sort</code> của [[Go (ngôn ngữ lập trình)|Go]] cung cấp các hàm <code>Search</code>, <code>SearchInts</code>, <code>SearchFloat64s</code>, và <code>SearchStrings</code>, lần lượt có chức năng thực hiện tìm kiếm nhị phân tổng quát, tìm kiếm các lát số nguyên, số thập phân dấu phẩy động và chuỗi ký tự.<ref>{{chú thích web | work = The Go Programming Language | url = http://golang.org/pkg/sort/ | title = Package sort | access-date = ngày 28 tháng 4 năm 2016 | archive-url = https://web.archive.org/web/20160425055919/https://golang.org/pkg/sort/ | archive-date = ngày 25 tháng 4 năm 2016 | url-status = live | df = dmy-all }}</ref>
* [[Java (ngôn ngữ lập trình)|Java]] cung cấp một bộ các phương thức static [[chồng hàm|chồng]] <code>binarySearch()</code> trong các lớp {{Javadoc:SE|java/util|Arrays}} và {{Javadoc:SE|java/util|Collections}} chứa trong gói <code>java.util</code> chuẩn, lần lượt có chức năng thực hiện tìm kiếm nhị phân trên các mảng trong Java và trên các <code>List</code>.<ref>{{chú thích web|title=java.util.Arrays|url=https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html|website=Java Platform Standard Edition 8 Documentation|publisher=[[Oracle Corporation]]|access-date =ngày 1 tháng 5 năm 2016|archive-url=https://web.archive.org/web/20160429064301/http://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html|archive-date=ngày 29 tháng 4 năm 2016|url-status=live|df=dmy-all}}</ref><ref>{{chú thích web|title=java.util.Collections|url=https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html|website=Java Platform Standard Edition 8 Documentation|publisher=[[Oracle Corporation]]|access-date =ngày 1 tháng 5 năm 2016|archive-url=https://web.archive.org/web/20160423092424/https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html|archive-date=ngày 23 tháng 4 năm 2016|url-status=live|df=dmy-all}}</ref>
* [[Microsoft]]'s [[.NET Framework]] 2.0 cung cấp các phiên bản static [[Lập trình tổng quát|tổng quát]] của thuật toán tìm kiếm nhị phân trong các lớp collection base. Ví dụ như phương thức <code>BinarySearch<T>(T[] array, T value)</code> trong <code>System.Array</code><ref>{{chú thích web|title=List<T>.BinarySearch method (T)|url=https://msdn.microsoft.com/en-us/library/w4e7fxsh%28v=vs.110%29.aspx|website=Microsoft Developer Network|access-date =ngày 10 tháng 4 năm 2016|archive-url=https://web.archive.org/web/20160507141014/https://msdn.microsoft.com/en-us/library/w4e7fxsh%28v=vs.110%29.aspx|archive-date=ngày 7 tháng 5 năm 2016|url-status=live|df=dmy-all}}</ref>
* Với [[Objective-C]], framework [[Cocoa (API)|Cocoa]] cung cấp phương thức <code>[https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/NSArray.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator: NSArray -indexOfObject:inSortedRange:options:usingComparator:]</code> trong Mac OS X từ bản 10.6 trở lên.<ref>{{chú thích web|title=NSArray|url=https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/index.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator:|website=Mac Developer Library|publisher=[[Apple Inc.]]|access-date =ngày 1 tháng 5 năm 2016|archive-url=https://web.archive.org/web/20160417163718/https://developer.apple.com/library/mac/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/index.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator:|archive-date=ngày 17 tháng 4 năm 2016|url-status=live|df=dmy-all}}</ref> Framework [[Core Foundation]] C của Apple cũng chứa hàm <code>[https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/Reference/reference.html#//apple_ref/c/func/CFArrayBSearchValues CFArrayBSearchValues()]</code>.<ref>{{chú thích web|title=CFArray|url=https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/index.html#//apple_ref/c/func/CFArrayBSearchValues|website=Mac Developer Library|publisher=[[Apple Inc.]]|access-date =ngày 1 tháng 5 năm 2016|archive-url=https://web.archive.org/web/20160420193823/https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/index.html#//apple_ref/c/func/CFArrayBSearchValues|archive-date=ngày 20 tháng 4 năm 2016|url-status=live|df=dmy-all}}</ref>
* [[Python (ngôn ngữ lập trình)|Python]] cung cấp mô đun <code>bisect</code>.<ref>{{chú thích web|title=8.6. bisect — Array bisection algorithm|url=https://docs.python.org/3.6/library/bisect.html#module-bisect|website=The Python Standard Library|publisher=Python Software Foundation|access-date =ngày 26 tháng 3 năm 2018|archive-url=https://web.archive.org/web/20180325105932/https://docs.python.org/3.6/library/bisect.html#module-bisect|archive-date=ngày 25 tháng 3 năm 2018|url-status=live|df=dmy-all}}</ref>
* Lớp Array của [[Ruby (ngôn ngữ lập trình)|Ruby]] có chứa phương thức <code>bsearch</code> có cả chức năng so khớp xấp xỉ.{{Sfn|Fitzgerald|2007|p=152}}

==Ghi chú và tham khảo==
<!-- Referencing conventions for this article: use CS1 templates, add book and monograph sources to the Works section and then cite them using Harvard citations, directly cite other sources. Source titles are in sentence case, but the first letter of proper nouns (e.g., "Bayesian") is capitalized. -->

=== Ghi chú ===
{{Notelist}}

=== Chú thích ===
{{tham khảo|30em}}

=== Tài liệu ===
{{columns-list|colwidth=30em|style=font-size:90%;|
<!-- * {{chú thích sách|last1=Alexandrescu|first1=Andrei|title=The D Programming Language|date=2010|publisher=Addison-Wesley Professional|location=Upper Saddle River, New Jersey|isbn=0-321-63536-1}}-->
* {{chú thích sách
| last = Bentley
| first = Jon
| authorlink = Jon Bentley (nhà khoa học máy tính)
| title = Programming pearls
|edition=2 | publisher = [[Addison-Wesley]]
| year = 2000
| isbn = 978-0-201-65788-3}}
* {{chú thích sách|last1=Butterfield|first1=Andrew|last2=Ngondi|first2=Gerard E.|title=A dictionary of computer science|url=https://archive.org/details/isbn_9780199688975|date=2016|publisher=[[Oxford University Press]]|location=Oxford, UK|isbn=978-0-19-968897-5|edition=7 }}
* {{chú thích sách | title=Data structures and algorithms | publisher=[[World Scientific]] | last1=Chang|first1=Shi-Kuo| year=2003 | location=Singapore | isbn=978-981-238-348-8 | volume=13 | work=Software Engineering and Knowledge Engineering}}
* {{chú thích sách
| last1 = Cormen
| first1 = Thomas H.
| author1-link=Thomas H. Cormen
| last2= Leiserson
| first2= Charles E.
| author2-link=Charles E. Leiserson
| last3= Rivest
| first3= Ronald L.
| author3-link=Ron Rivest
| last4= Stein
| first4=Clifford
| author4-link=Clifford Stein
|title=Introduction to algorithms
| year = 2009
|edition=3 | publisher = MIT Press and McGraw-Hill
| isbn = 978-0-262-03384-8
| title-link = Introduction to Algorithms
}}
* {{chú thích sách|last1=Fitzgerald|first1=Michael|title=Ruby pocket reference|date=2007|publisher=[[O'Reilly Media]]|location=Sebastopol, California|isbn=978-1-4919-2601-7}}
* {{chú thích sách|last1=Goldman|first1=Sally A.|last2=Goldman|first2=Kenneth J.|title=A practical guide to data structures and algorithms using Java|date=2008|publisher=[[CRC Press]]|location=Boca Raton, Florida|isbn=978-1-58488-455-2}}
* {{chú thích sách |last1=Kasahara |first1=Masahiro |last2=Morishita |first2=Shinichi |title=Large-scale genome sequence processing |date=2006 |publisher=Imperial College Press |location=London, UK |isbn=978-1-86094-635-6 }}
* {{chú thích sách|last=Knuth|first=Donald|year=1997|authorlink=Donald Knuth|title=Fundamental algorithms|series=[[The Art of Computer Programming]]|volume=1|edition=3 |location=Reading, MA|publisher=Addison-Wesley Professional|isbn=978-0-201-89683-1}}
* {{chú thích sách|last=Knuth|first=Donald|year=1998|authorlink=Donald Knuth|title=Sorting and searching|series=[[The Art of Computer Programming]]|volume=3|edition=2 |location=Reading, MA|publisher=Addison-Wesley Professional|isbn=978-0-201-89685-5}}
* {{chú thích sách|last=Knuth|first=Donald|year=2011|authorlink=Donald Knuth|title=Combinatorial algorithms|series=[[The Art of Computer Programming]]|volume=4A|edition=1 |location=Reading, MA|publisher=Addison-Wesley Professional|isbn=978-0-201-03804-0}}
<!-- * {{chú thích sách|last1=Leiss|first1=Ernst|title=A Programmer's Companion to Algorithm Analysis|url=https://archive.org/details/programmerscompa0000leis|date=2007|publisher=CRC Press|location=Boca Raton, Florida|isbn=1-58488-673-0}} -->
* {{chú thích sách|last1=Moffat|first1=Alistair|last2=Turpin|first2=Andrew|title=Compression and coding algorithms|url=https://archive.org/details/compressioncodin0000moff|date=2002|publisher=Kluwer Academic Publishers|location=Hamburg, Germany|isbn=978-0-7923-7668-2|doi=10.1007/978-1-4615-0935-6}}
* {{chú thích sách|last1=Sedgewick|first1=Robert|last2=Wayne|first2=Kevin|authorlink1=Robert Sedgewick (computer scientist)|title=Algorithms|date=2011|publisher=Addison-Wesley Professional|location=Upper Saddle River, New Jersey|isbn=978-0-321-57351-3|edition=4 |url=http://algs4.cs.princeton.edu/home/}} Condensed web version {{open access}}; book version {{closed access}}.
* {{chú thích sách|last1=Stroustrup|first1=Bjarne|authorlink=Bjarne Stroustrup|title=The C++ programming language|edition=4 |date=2013|publisher=Addison-Wesley Professional|location=Upper Saddle River, New Jersey|isbn=978-0-321-56384-2}}
}}

[[Thể loại:Giải thuật tìm kiếm]]