Độ phức tạp của binary search

Giả sử cần tìm trong array n phần tử.

Giả sử Binary Search sẽ kết thúc sau k vòng lặp.

Sau mỗi lần lặp, số lượng phần tử của array sẽ giảm đi 1/2

Ở lần lặp 1: Độ dài array là n

Ở lần lặp 2: Độ dài array là n/2

Ở lần lặp 3: Độ dài array là n/2 * 1/2 = n/4

Ở lần lặp k: Độ dài array là n/2^k

Sau k phép chia thì độ dài array sẽ về 1.

DO đó độ dài array = n/2^k = 1

=> n=2^k

Lúc này thực hiện Log cả 2 vế 

Log2(n) = log2(2^k)

=> Log2(n) = klog2(2)=k

Như vậy k=log2(n)

Như vậy độ phức tạp thời gian của Binary Search là : log2(n).