Know this before you start: “Classic search in a sorted array”

Binary search in a sorted array

Look at the middle: it tells you which half the target can't be in. Each step halves what's left, so a million items take about 20 steps.

The idea

In a sorted array, if the middle value is smaller than the target, everything to its left is smaller too: throw that half away. If it's bigger, throw the right half away.

Keep two indexes, lo and hi, around the part that could still hold the target, and narrow them until you find it or they cross. Halving each time is O(log n).

See it step by step

Find 23 in [2, 5, 8, 12, 16, 23, 38]

lo = 0, hi = 6, mid = 3 → 12 < 23 → lo = 4
mid = 5 → 23 → found at index 5, after 2 looks instead of 6.

In code (Python)

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
        else:
            hi = mid - 1
    return -1

print(binary_search([2, 5, 8, 12, 16, 23, 38], 23))   # 5
print(binary_search([2, 5, 8], 6))                     # -1

O(log n) time, O(1) space.

When you'll use it

Sorted data and “find”, “search”, “insert position”, or any time a yes/no answer flips once as you move right.

Common mistakes

lo = mid instead of mid + 1: an endless loop.
Mixing `while lo <= hi` with the wrong updates for that template.