Binary Search: The Pattern That Powers a Hundred Problems

Binary search is the algorithm interviewers love and beginners get wrong. The idea is trivial — halve the search space each step — but the implementation trips up almost everyone the first time. The off-by-one bugs are real; this post will walk you past them.

We will also cover the pattern that turns binary search from “find an element in a sorted array” into a general tool: binary search on the answer.

The classic template

Given a sorted array arr and a target x, find the index of x or return -1.

index:  0   1   2   3   4   5   6   7
arr:  [ 1,  3,  4,  5,  7,  9,  11, 13 ]
step 1: lo=0, hi=7, mid=3, arr[mid]=5 < 7  → lo = mid + 1 = 4
↑           ↑
lo         hi
step 2: lo=4, hi=7, mid=5, arr[mid]=9 > 7  → hi = mid - 1 = 4
↑   ↑
lo  hi
step 3: lo=4, hi=4, mid=4, arr[mid]=7 == 7  → return 4
↑
found!

def binary_search(arr, x):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == x:
            return mid
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 4, 5, 7, 9, 11, 13], 7))
# output: 4
print(binary_search([1, 3, 4, 5, 7, 9, 11, 13], 6))
# output: -1

Three rules keep you out of trouble:

1. hi = len(arr) - 1 — hi is inclusive.
2. while lo <= hi — include the equal case.
3. After the comparison, move past mid: mid + 1 or mid - 1. Never just mid.

If you ever write lo = mid without the + 1, you will get an infinite loop when lo == hi.

The “half-open” template — lower_bound

There is a second template that finds the leftmost position where x could be inserted to keep the array sorted. It is the basis of bisect.bisect_left and is often easier to reason about for “find the first element matching X” problems.

def lower_bound(arr, x):
    lo, hi = 0, len(arr)        # hi is exclusive!
    while lo < hi:               # strict less-than
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid             # no -1!
    return lo

print(lower_bound([1, 3, 5, 5, 5, 7], 5))
# output: 2
print(lower_bound([1, 3, 5, 5, 5, 7], 6))
# output: 5

Notice how hi is exclusive (len(arr)), the loop uses <, and we set hi = mid rather than mid - 1. Pick one template and stick with it; mixing them is how bugs are born.

Python’s bisect module

For real code, don’t write either template. Use bisect:

import bisect

arr = [1, 3, 5, 5, 5, 7]
print(bisect.bisect_left(arr, 5))   # output: 2
print(bisect.bisect_right(arr, 5))  # output: 5

# Maintain a sorted list as you insert
sl = []
for x in [5, 2, 8, 1]:
    bisect.insort(sl, x)
print(sl)
# output: [1, 2, 5, 8]

bisect_left and bisect_right differ only on duplicates: left returns the first valid position, right returns one past the last.

You can build a “search for exact match” on top:

def contains(arr, x):
    i = bisect.bisect_left(arr, x)
    return i < len(arr) and arr[i] == x

Binary search on the answer

This is the pattern that elevates binary search from “search in a sorted array” to “solve any monotonic decision problem.”

The setup: you have an answer space (e.g. integers from 1 to 10^9) and a predicate can_do(x) that is monotonic — once it becomes True as x increases, it stays True (or vice versa). You binary search for the boundary.

Template:

def binary_search_answer(lo, hi, can_do):
    while lo < hi:
        mid = (lo + hi) // 2
        if can_do(mid):
            hi = mid          # mid works; maybe something smaller does too
        else:
            lo = mid + 1
    return lo

When the loop exits, lo == hi and it is the smallest x for which can_do(x) is True. We will use this for the Koko problem below.

Common off-by-one traps

• Integer overflow: in some languages, (lo + hi) // 2 overflows. Write lo + (hi - lo) // 2. In Python this doesn’t matter, but the habit is good.
• Wrong loop condition: while lo < hi with hi = len(arr) - 1 will miss the last element. Use either [lo, hi] inclusive with <=, or [lo, hi) half-open with <.
• Moving mid wrong: with the classic [lo, hi] template, always do mid + 1 and mid - 1. With the half-open template, do mid + 1 and mid.
• Infinite loops: caused by lo = mid (instead of mid + 1) when lo == hi - 1.

Practice problems

1. Classic Binary Search

Already shown above. Make sure you can write it from memory in under a minute.

2. First Bad Version

You have an API isBadVersion(n). Versions go from 1 to n; once one is bad, all later ones are bad. Find the first bad version.

This is binary search on the answer with can_do = isBadVersion:

def first_bad_version(n, is_bad):
    lo, hi = 1, n
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_bad(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

# example with bad starting at 4
print(first_bad_version(10, lambda v: v >= 4))
# output: 4

3. Search in Rotated Sorted Array

The array is sorted, then rotated. Find a target in O(log n).

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

print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))
# output: 4

The key insight: at any point, at least one half is fully sorted. Decide which, check whether the target lies in it, and recurse on the appropriate side.

4. Find Minimum in Rotated Sorted Array

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1      # min is in right half
        else:
            hi = mid           # min is in left half (including mid)
    return nums[lo]

print(find_min([4, 5, 6, 7, 0, 1, 2]))
# output: 0

5. Search a 2D Matrix

A matrix where each row is sorted and the first element of each row is greater than the last element of the previous row. Effectively one long sorted array.

def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        val = matrix[mid // n][mid % n]
        if val == target:
            return True
        if val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

print(search_matrix([[1, 3, 5], [7, 9, 11], [13, 15, 17]], 9))
# output: True

The divmod trick maps a flat index back to row/column.

6. Koko Eating Bananas

Koko eats bananas at a chosen speed k per hour. Given piles and h hours, find the minimum k that finishes all piles in time. The classic binary search on the answer.

import math

def min_eating_speed(piles, h):
    def can_finish(k):
        return sum(math.ceil(p / k) for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(min_eating_speed([3, 6, 7, 11], 8))
# output: 4

can_finish is monotonic: if speed k works, every larger speed works too. We binary search for the smallest True.

Recap

You now know:

• The classic [lo, hi] inclusive template — while lo <= hi, mid + 1, mid - 1.
• The half-open [lo, hi) template — while lo < hi, mid + 1, mid.
• bisect.bisect_left and bisect.bisect_right for real Python code.
• The binary search on the answer pattern for monotonic predicates.
• Common off-by-one traps and how to avoid them.

Next steps

Binary search exploits monotonicity. Greedy algorithms exploit a different kind of structure: locally best choices that happen to be globally optimal. That is the next post.

→ Next: Greedy Algorithms — When Locally Best Wins Globally

Questions or feedback? Email codeloomdevv@gmail.com.