BINARY-SEARCH(A, x)- 1
lo ← 0, hi ← n ▷ the range is A[lo .. hi − 1] - 2
while lo < hi do - 3
mid ← lo + ⌊(hi − lo) / 2⌋ ▷ no overflow, unlike ⌊(lo + hi) / 2⌋ - 4
if A[mid] < x then - 5
lo ← mid + 1 ▷ x is not in A[lo .. mid] - 6
else if A[mid] > x then - 7
hi ← mid ▷ x is not in A[mid .. hi − 1] - 8
else return mid - 9
return NIL