Linear and binary search

Why it matters

Searching is everywhere: finding a user by ID, a word in a dictionary, the first log line after a timestamp, the right version that introduced a bug (git bisect is binary search). Knowing when you can do better than "look at everything" is one of the most practical skills in this course, and binary search is a classic interview question because it is short but easy to get subtly wrong.

Linear search

Linear search checks each item in turn until it finds the target or runs out of items.

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

• Works on any list, sorted or not.
• Worst case: the target is last or missing, so it looks at all n items. O(n).
• Python's items.index(x) and x in items are linear searches under the hood.

For a short list, or a list you search only once, linear search is the right tool. Sorting first costs O(n log n), which is more than one O(n) scan.

Binary search

If the list is sorted, you can do far better. Look at the middle item:

• If it is the target, you are done.
• If the target is bigger, it can only be in the right half.
• If the target is smaller, it can only be in the left half.

Each comparison throws away half of what is left. A million items need at most about 20 comparisons. That is O(log n).

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1      # target is to the right of mid
        else:
            high = mid - 1     # target is to the left of mid
    return -1

low and high mark the part of the list that could still hold the target. The loop runs while that range is not empty (low <= high).

Worked example

Search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (10 items, indexes 0–9).

Three looks instead of six. Now search for 20: after step 2 we check index 5 (23 > 20, high = 4). Now low = 5 > high = 4, the range is empty, and we return -1.

Edge cases to test

Binary search bugs hide in the edges, so always try:

• an empty list (high starts at -1, the loop never runs, return -1),
• a one-item list, target present and absent,
• the first and last items,
• a target smaller than everything and larger than everything,
• a target that would sit between two items.

Common mistakes

• Using < instead of <=. With while low < high, a one-item range is never checked, so the search misses targets.
• Writing low = mid or high = mid. The range may stop shrinking and the loop runs forever. Move past mid with + 1 / - 1.
• Searching an unsorted list. Binary search gives wrong answers, not errors, on unsorted data.
• Slicing. binary_search(items[mid:], target) copies half the list each time, which is O(n) work per step and also breaks the returned index. Move low and high instead.

In the standard library

Python's bisect module does binary search for you. bisect.bisect_left(items, x) returns the index where x would be inserted to keep the list sorted. If that index is inside the list and items[i] == x, you found it. Writing your own once is how you learn to trust and debug the library version.

import bisect
items = [2, 5, 8, 12, 16]
i = bisect.bisect_left(items, 12)   # 3

Quick recap

• Linear search: any list, O(n).
• Binary search: sorted list only, halves the range each step, O(log n).
• Keep low/high bounds, loop while low <= high, move past mid.
• Test empty, one item, first, last, and missing values.

Try it

In the Do tab, write both searches. One check counts how many items your binary search looks at in a 500,000-item list, so a disguised linear scan will not pass.