Binary Search

Discard half every step

On a sorted array, compare the target to the middle element. If the target is larger, the whole left half (including mid) is irrelevant — move left past it. Otherwise drop the right half. Each step halves the search space: O(log n).

Iterative template

Use left <= right and mid = left + (right-left)//2 to avoid overflow in other languages.

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

Output:

binary_search([10,20,30,40,50,60,70,80], 60) -> 5

Dry run: find 60

[10 20 30 40 50 60 70 80]

• Step 1: lo=0 hi=7 mid=3 → arr[3]=40 < 60 → lo=4
• Step 2: lo=4 hi=7 mid=5 → arr[5]=60 → found at index 5

Quick check: Binary search requires the data to be...

• Sorted (or monotonic on the predicate)
• Stored in a hash map
• Of prime length