Tìm kiếm nhị phân
Hiệu suất

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.
Trong trường hợp tệ nhất, thuật toán thực hiện 



⌊

log

2


⁡
(
n
)
+
1
⌋


{\textstyle \lfloor \log _{2}(n)+1\rfloor }

 lần lặp so sánh, trong đó 



⌊
⌋


{\textstyle \lfloor \rfloor }

 là ký hiệu của 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à 




log

2




{\textstyle \log _{2}}

 là phép 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 



⌊

log

2


⁡
(
n
)
+
1
⌋


{\textstyle \lfloor \log _{2}(n)+1\rfloor }

 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 



n


{\textstyle n}

 ở dạng 




2

α


−
1


{\textstyle 2^{\alpha }-1}

 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 



⌊

log

2


⁡
(
n
)
+
1
⌋


{\textstyle \lfloor \log _{2}(n)+1\rfloor }

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 



⌊

log

2


⁡
(
n
)
⌋


{\textstyle \lfloor \log _{2}(n)\rfloor }

 phép lặp, ít hơn trường hợp tệ nhất một phép.
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  \lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n phép lặp khi phần tử cần tìm có mặt trong mảng, hay xấp xỉ bằng  \log _{2}(n)-1. 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  \lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1) 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.
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.
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. 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ể.