Function BInary_search(k,r,a,X);

If k>r then

tg:=0 then //khong tim thay

else 

m:=(k+r)div 2;

If a[m]=X;  //tim thay 

Else

If X<a[m] then 

 binary_search(k,m-1,a,X);

else 

binary_search(m+1,r,a,X);

end;

return tg;

Thời gian thực hiện:

Thuận lợi nhất khi tìm thấy ngay ở giữa: O(1)

Không thuận lợi khi phải gọi đệ qui, gọi thời gian cần thực hiện trong trường hợp này là:

W(r – k + 1)

Với lần gọi ban đầu: k = 1, r = n

Có W(n – 1 + 1) = W(n) = 1 + W(n/2)

= 1 + 1 + W(n/4)… = 1 + 1 + … + W(n/2x)

Dừng khi (n/2x) = 1 vì W(1) = 1

Mà (n/2x) = 1 ó x = log2n

Tức là ta phải gọi đệ qui log2n lần

=> Độ phức tạp là O(log2n)