Beginner 13 min

Searching

Linear search, binary search and how to search an answer space.

What you will learn

Write binary search without off-by-one bugs
Know when data must be sorted
Use the bisect module

Searching means finding an item, or its position, inside a collection. How you do it depends on one question: is the data sorted? Sorted data lets you throw away half the possibilities at every step.

Linear search

Check items one by one. It works on any data and takes O(n) time, so it is perfectly fine for small lists or one-off lookups.

def linear_search(items, target):
    for i, x in enumerate(items):
        if x == target:
            return i
    return -1

print(linear_search([7, 3, 9, 1], 9))

Output

Binary search

On a sorted list, compare the target with the middle element. If it is smaller, the answer must be in the left half; if larger, the right half. Each comparison halves the search space, giving O(log n): a billion items need about 30 checks.

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

nums = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(nums, 9), binary_search(nums, 4))

Output

4 -1

The details that cause bugs: the loop condition is lo <= hi (the range is inclusive on both ends), and the updates are mid + 1 and mid - 1 so the range always shrinks. Getting either wrong produces an infinite loop or a missed element.

Finding a boundary

A very common variant: find the first position where a condition becomes true, or the insertion point for a value. Python ships this as bisect.

from bisect import bisect_left, bisect_right

a = [1, 2, 2, 2, 5, 8]
print(bisect_left(a, 2))    # 1  first index of 2
print(bisect_right(a, 2))   # 4  index after the last 2
print(bisect_right(a, 2) - bisect_left(a, 2))   # count of 2s

Output

1
4
3

Searching the answer

Binary search is not just for lists. Whenever the answer lies in a range and a yes/no test is monotonic (false, false, false, true, true, true), you can binary search on the answer. Example: the smallest speed that lets you finish a task in time.

import math

def min_speed(piles, hours):
    """Smallest k so that ceil(pile/k) summed over piles <= hours."""
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if sum(math.ceil(p / mid) for p in piles) <= hours:
            hi = mid            # mid works, try smaller
        else:
            lo = mid + 1        # too slow
    return lo

print(min_speed([3, 6, 7, 11], 8))

Output

Prerequisite

Binary search on unsorted data gives wrong answers silently. If you must search repeatedly, sorting once (O(n log n)) or using a hash set (O(1) lookup) is often better.

Try it yourself

Write first_true(a) that receives a list of booleans like [False, False, True, True] (all False first, then all True) and returns the index of the first True, or -1.

Show solution

def first_true(a):
    lo, hi, ans = 0, len(a) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid]:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

print(first_true([False, False, True, True]))   # 2