Binary Search

The guessing game

Think of it like this: “I'm thinking of a number from 1 to 100.” A smart guesser says 50. “Higher.” 75. “Lower.” 62... Each guess throws away half of the numbers that are left, so you need at most 7 guesses.

Binary search does exactly this on a sorted list: look at the middle item, then keep only the half where the target could be.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1         # target is in the right half
        else:
            high = mid - 1        # target is in the left half
    return -1

nums = [3, 8, 15, 21, 34, 42, 57, 70, 88]
print(binary_search(nums, 42))
print(binary_search(nums, 5))

Output

5
-1

Watch it halve

nums = list(range(0, 1000, 5))      # 200 sorted numbers
target = 735
low, high = 0, len(nums) - 1
step = 0
while low <= high:
    step += 1
    mid = (low + high) // 2
    print(f"step {step}: look at index {mid} (value {nums[mid]})")
    if nums[mid] == target:
        break
    if nums[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

Output

step 1: look at index 99 (value 495)
step 2: look at index 149 (value 745)
step 3: look at index 124 (value 620)
step 4: look at index 136 (value 680)
step 5: look at index 142 (value 710)
step 6: look at index 145 (value 725)
step 7: look at index 147 (value 735)

200 items, found in a handful of steps. A million items would take only about 20. That's O(log n).

Common mistake: Binary search only works on sorted data. On an unsorted list it gives wrong answers without any error.