Binary Search

The Idea

On sorted data, compare the target with the middle element and throw away the half that cannot contain it. Repeat until one candidate remains. That halving gives you O(log n).

Real-World Example

Finding "Nadia" in your phone contacts. You never scroll from A; you jump near the middle, land somewhere around M, and instantly ignore everything before it. Two or three jumps later you are there.

The Code

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1      # target must be in the right half
        else:
            hi = mid - 1      # target must be in the left half
    return -1

print(binary_search([2, 5, 8, 12, 16, 23], 16))   # 4

nums = [1, 3, 5, 7, 9]
lo, hi = 0, 4
mid = (lo + hi) // 2
# nums[mid] is 5 and the target is 9 -> search right
lo = ___