DSA Binary Search

Binary search looks for a target in a sorted list by halving the range still in play. Each step discards half the remaining values.

Pick the middle

The middle index sits halfway between the two ends. Its value decides the next move.

nums = [2, 5, 8, 12, 16, 23, 38, 56]
lo = 0
hi = len(nums) - 1
mid = (lo + hi) // 2
print("mid index:", mid)
print("mid value:", nums[mid])

Halve once by hand

The target 23 beats the middle value 12. The left half is discarded at once.

nums = [2, 5, 8, 12, 16, 23, 38, 56]
lo = 0
hi = len(nums) - 1
mid = (lo + hi) // 2
if 23 > nums[mid]:
    lo = mid + 1
else:
    hi = mid - 1
print("new lo:", lo)
print("new hi:", hi)

Example

nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

def binary_search(target):
    lo = 0
    hi = len(nums) - 1
    checks = []
    while lo <= hi:
        mid = (lo + hi) // 2
        checks.append(nums[mid])
        if nums[mid] == target:
            return mid, checks
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, checks

for target in [23, 90]:
    index, checks = binary_search(target)
    print("target:", target, "checks:", checks, "index:", index, "comparisons:", len(checks))

Key points

Binary search works only on a sorted list.
The middle value splits the current range in two.
One comparison decides which half survives.
The invariant is the promise that the target, if present, lies inside the current range.
Ten values need at most four comparisons, as the counts below show.

In this example, the search for 23 checks 16, then 56, then 23 itself. Each check discards half the range. The missing 90 needs four checks before the range empties. Ten values never need more than four comparisons.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

def binary_search(target):
    lo = 0
    hi = len(nums) - 1
    checks = []
    while lo <= hi:
        mid = (lo + hi) // 2
        checks.append(nums[mid])
        if nums[mid] == target:
            return mid, checks
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, checks

for target in [23, 90]:
    index, checks = binary_search(target)
    print("target:", target, "checks:", checks, "index:", index, "comparisons:", len(checks))

Exercise

The range runs from lo = 2 to hi = 9. What is the middle index?

3 4 5 6