Algorithms · Lesson 1 of 6

Searching

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

• Beginner
• 13 min read
• 3 objectives

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.

Finding a needle, faster

Searching is the most common job in computing. If you have no order to exploit you must check items one by one. If the data is sorted you can do far better by using the order, the way you open a dictionary near the middle rather than at page one. The idea behind binary search is to throw away half of the remaining possibilities with every question.

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))

2

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))

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

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))

4

How many guesses to find a number from 1 to 1,000?

Guess the middle (500). Told "higher", the answer is now in 501-1000, half the size. Repeat. You need at most 10 guesses because 2 to the power 10 is 1,024. That is O(log n).

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

numbers = list(range(1, 1001))
print(binary_search(numbers, 777))
print(binary_search(numbers, 5000))

(776, 8)
(-1, 10)

It found 777 in at most 10 steps out of 1,000 items. The same code finds an item among a billion in about 30 steps.

The three things that go wrong

• The data must be sorted. On unsorted data binary search silently returns wrong answers.
• Off-by-one on the boundaries: use lo <= hi and move to mid + 1 / mid - 1.
• Infinite loops: if you set lo = mid instead of mid + 1, the range may never shrink.

Use the library when you can

from bisect import bisect_left

prices = [10, 20, 20, 30, 45]
print(bisect_left(prices, 20))    # first position where 20 fits
print(bisect_left(prices, 25))    # where 25 would be inserted

1
3

Key takeaways

• Linear search checks each item: O(n), works on any data.
• Binary search halves the range each step: O(log n), needs sorted data.
• Be careful with boundaries; prefer bisect in real code.

# Write your solution here