Binary Search

Foundation drill for this topic

Drill #51 — Binary search template

Easy Binary Search

In plain English: Look for a specific number in a sorted list by repeatedly cutting the search area in half.

Each comparison eliminates half the remaining elements — log2(n) halves is all you ever need to find any element or prove it absent.

Prompt

Given a sorted array and a target value, return the index of the target or -1 if not found.

Try to write it from scratch before scrolling down.

Solution

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo &lt;= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        elif a[mid] &lt; target:
            lo = mid + 1  # target is in right half
        else:
            hi = mid - 1  # target is in left half
    return -1

# Test: binary_search([1,3,5,7,9,11], 7) == 3
# Test: binary_search([1,3,5,7,9,11], 4) == -1

O(log n) time · O(1) space

Related Micro Drills

Quick recall drills to reinforce this pattern.

46 Binary search template Search 15s

The standard binary search template. Foundation for all logarithmic search problems.

lo, hi = 0, len(a) - 1
while lo &lt;= hi:
    mid = lo + (hi - lo) // 2
    if a[mid] == target: return mid
    elif a[mid] &lt; target: lo = mid + 1
    else: hi = mid - 1

274 Find peak element (binary search) Search 10s

Move toward the higher neighbor — a peak must exist on that side. Uses lo < hi (not <=) and hi = mid (not mid-1).

lo, hi = 0, len(a) - 1
while lo &lt; hi:
    mid = (lo + hi) // 2
    if a[mid] &lt; a[mid + 1]:
        lo = mid + 1
    else:
        hi = mid
return lo

48 Left boundary (bisect_left) Search 15s

Left boundary search finds the first occurrence. Key for range queries and count problems.

lo, hi = 0, len(a)
while lo &lt; hi:
    mid = lo + (hi - lo) // 2
    if a[mid] &lt; target: lo = mid + 1
    else: hi = mid
return lo

See all drills in Binary Search →