Linear & Binary Search

Prev Next

Searching means finding whether (and where) a target value exists inside a collection. The two classic approaches sit at opposite ends of a trade-off: linear search works on anything, in any order, at the cost of checking every element in the worst case. Binary search is dramatically faster, but only works if the data is already sorted. Both show up constantly in interviews — not because you'll hand-write binary search in production, but because the "cut the search space in half each time" idea reappears everywhere in DSA.

Linear Search: O(n)

Check every element from the start until you find the target or run out of elements. No ordering requirement at all — it works on any list.

def linear_search(items, target):
    for index, value in enumerate(items):
        if value == target:
            return index         # found it -- return its position
    return -1                      # not present anywhere in the list


print(linear_search([4, 2, 9, 7], 9))   # 2
print(linear_search([4, 2, 9, 7], 5))   # -1

Time complexity: O(n) worst case — the target might be the last element checked, or absent entirely, forcing a full scan. Space complexity: O(1) — only a loop index and value are held at any time.

Binary Search: O(log n) on Sorted Data

If the list is sorted, you don't need to check every element. Look at the middle element: if it's the target, you're done. If the target is smaller, it can only be in the left half, so discard the right half entirely — and vice versa. Each comparison throws away half of what's left, which is exactly why it takes only O(log n) comparisons to narrow a list of a billion elements down to one.

def binary_search(items, target):
    low, high = 0, len(items) - 1

    while low <= high:
        mid = (low + high) // 2              # NOT (low + high) / 2 -- must stay an int index
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1                   # target must be to the right of mid
        else:
            high = mid - 1                  # target must be to the left of mid

    return -1                              # low > high -- search space exhausted, not found


sorted_items = [2, 4, 7, 9, 12, 18, 23]
print(binary_search(sorted_items, 18))   # 5
print(binary_search(sorted_items, 6))    # -1

Time complexity: O(log n) — every iteration halves the remaining search range, so it takes about log₂(n) iterations to shrink the range to nothing. Space complexity: O(1) — only two or three index variables are tracked, regardless of list size.

The classic off-by-one bug: using low < high instead of low <= high silently skips checking the case where low == high (exactly one candidate left), which can wrongly report "not found" for a target that's actually there. Similarly, setting bounds to mid instead of mid + 1 / mid - 1 can leave the already-checked middle element in the range forever, causing an infinite loop. Always trace through a 1-element and a 2-element list by hand when you write this from scratch.

Recursive Binary Search

The same halving idea, expressed as a function that calls itself on a shrinking sub-range instead of looping. Purely a style choice — the iterative version above is preferred in production Python because it avoids the (small, but real) function-call overhead and Python's relatively low default recursion limit, but the recursive form often reads closer to the "divide and conquer" idea itself.

def binary_search_recursive(items, target, low=0, high=None):
    if high is None:
        high = len(items) - 1

    if low > high:
        return -1                          # base case -- search space is empty

    mid = (low + high) // 2
    if items[mid] == target:
        return mid
    elif items[mid] < target:
        return binary_search_recursive(items, target, mid + 1, high)
    else:
        return binary_search_recursive(items, target, low, mid - 1)

Time complexity: O(log n) — identical reasoning to the iterative version, just expressed as recursive calls instead of loop iterations. Space complexity: O(log n) — unlike the iterative version, each recursive call adds a stack frame, and there are about log₂(n) of them before hitting the base case.

The Production Tool: Python's bisect Module

You will basically never hand-write binary search in real Python code — the standard library's bisect module already does it, in C, correctly, with the edge cases handled. bisect.bisect_left(items, target) returns the leftmost index where target could be inserted to keep the list sorted; if that index actually holds target, you've found it.

import bisect

sorted_items = [2, 4, 7, 9, 12, 18, 23]

index = bisect.bisect_left(sorted_items, 9)
if index < len(sorted_items) and sorted_items[index] == 9:
    print(f"found at {index}")   # found at 3

Time complexity: O(log n) — bisect is implemented as a binary search internally. Space complexity: O(1) — no extra structure beyond the two index bounds it tracks internally.

Rule of thumb: write binary search by hand to learn it and to answer interview questions, but reach for bisect the moment you need this in a real codebase — it's battle-tested and handles every boundary case correctly.

Worked Problem: First and Last Occurrence With Duplicates

Given a sorted list that may contain duplicates, find the first and last index of a target value. Plain binary search stops at any matching index, which might land in the middle of a run of duplicates. The fix: after landing on a match, keep searching in the direction that could reveal an earlier (or later) occurrence, instead of returning immediately.

def find_first(items, target):
    low, high, result = 0, len(items) - 1, -1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            result = mid            # record this match, but keep looking to the LEFT
            high = mid - 1       # for an even earlier occurrence
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result


def find_last(items, target):
    low, high, result = 0, len(items) - 1, -1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            result = mid            # record this match, but keep looking to the RIGHT
            low = mid + 1        # for an even later occurrence
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result


data = [1, 3, 3, 3, 5, 7, 7, 9]
print(find_first(data, 3), find_last(data, 3))   # 1 3
print(find_first(data, 7), find_last(data, 7))   # 5 6

Trace find_first(data, 3) on [1,3,3,3,5,7,7,9]: mid=3 (value 3) matches -- record result=3, search left with high=2. mid=1 (value 3) matches -- record result=1, search left with high=0. mid=0 (value 1) is less than 3, so low=1. Now low > high, loop ends with the last recorded result: 1, the true first index of value 3.

Time complexity: O(log n) for each of find_first and find_last — the "keep narrowing after a match" trick still discards half the remaining range every step, it just doesn't stop at the first match. Space complexity: O(1) — the same three tracked variables as plain binary search.

Next up: Bubble, Selection & Insertion Sort covers the three classic O(n²) sorting algorithms every list needs to be in order before binary search even applies.

Prev Next