visualization

Binary Search

Half the candidates die on every comparison.

nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 99] · target = 16step 1/9

Sorted array of 11 values. lo=0, hi=10 — all 11 indices are still candidates for 16.

pseudocode

lo, hi = 0, len(nums) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if nums[mid] == target: return mid
    elif nums[mid] < target:
        lo = mid + 1   # kill left half
    else:
        hi = mid - 1   # kill right half