NOA Labs

Searching Algorithms

Linear vs binary search, why binary search needs sorted data, and solving search in a rotated sorted array.

Linear search: the baseline

Linear search checks every element one at a time, in order, until it finds the target or runs out of list. It's the most basic search strategy possible — and it's the right one whenever you have no guarantee the data is organized in any particular way.

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

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

This runs in O(n) in the worst case (the target is last, or absent entirely) — every element might need to be checked. Its one real advantage is that it makes no assumptions whatsoever about the data: unsorted, sorted, doesn't matter, it works identically either way.

Binary search: needs sorted data

Binary search is dramatically faster, but it comes with a requirement: the data must already be sorted.

Analogy: guessing a hidden number between 1 and 100 when you're told, after each guess, whether the answer is higher or lower. The smart strategy is to always guess the middle of the remaining range — 50 first, then 25 or 75 depending on the feedback, and so on — eliminating half the remaining possibilities with every guess. That's binary search exactly: compare the target to the middle element, and based on whether it's smaller or larger, throw away the half of the array that couldn't possibly contain it.

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

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1        # target must be in the right half, if it's here at all
        else:
            high = mid - 1       # target must be in the left half, if it's here at all

    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))   # 3

Tracing it on [1, 3, 5, 7, 9, 11] with target 7: low=0, high=5, mid=2, arr[2]=5 < 7 → search the right half, low=3. Now low=3, high=5, mid=4, arr[4]=9 > 7 → search the left half, high=3. Now low=3, high=3, mid=3, arr[3]=7 — found it, return 3. Just three comparisons, and the search space was cut in half at every step.

This gives O(log n) time — each comparison eliminates half of what's left, so for a list of a million elements, binary search needs at most about 20 comparisons, versus up to a million for linear search in the worst case. That gap only widens as the data grows.

The gotcha: binary search on unsorted data fails silently

This is worth stating plainly because it's such a common trap: if you run binary search on unsorted data, it does not raise an error — it just returns a wrong answer, because the entire "go left or go right" logic assumes the array is ordered. Worse, it might happen to return the correct answer on some unsorted test inputs purely by luck, making the bug easy to miss until it fails on real data.

If your data isn't already sorted and you only need to search it once, sorting first costs O(n log n) — at that point, a single O(n) linear search might actually be cheaper overall than sorting plus an O(log n) binary search. Binary search earns its keep when the data is already sorted, or when you'll search the same collection many times, letting the one-time O(n log n) sorting cost be amortized across many fast searches.

A recursive version

Binary search can also be written recursively — each call handles a strictly smaller range, with the base case being an empty range:

Python
def binary_search_recursive(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low > high:
        return -1                       # base case: nothing left to search

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

print(binary_search_recursive([1, 3, 5, 7, 9, 11], 7))   # 3

This is the same algorithm, just expressed through recursion instead of a while loop — and it's a preview of a bigger idea: binary search is a textbook example of divide and conquer, a strategy the next-but-one page covers in its own right.

Classic problem: search in a rotated sorted array

A rotated sorted array starts out sorted, then gets "rotated" at some unknown pivot point — for example, [0, 1, 2, 4, 5, 6, 7] rotated becomes [4, 5, 6, 7, 0, 1, 2]. The array as a whole is no longer sorted, so plain binary search's "compare to the middle" logic can't be applied directly — and yet the array still has enough structure to search it in O(log n).

The key insight: at least one of the two halves around any midpoint is always properly sorted. Check which half is sorted first, then check whether the target could possibly lie within that sorted half's value range — if so, search there; if not, the target (if present at all) must be in the other half.

Python
def search_rotated(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid

        if arr[low] <= arr[mid]:                      # left half is sorted
            if arr[low] <= target < arr[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:                                          # right half is sorted
            if arr[mid] < target <= arr[high]:
                low = mid + 1
            else:
                high = mid - 1

    return -1


print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))   # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))   # -1 (not present)

Tracing the first call, arr=[4, 5, 6, 7, 0, 1, 2], target 0: low=0, high=6, mid=3, arr[3]=7. Is the left half sorted? arr[0]=4 <= arr[3]=7, yes. Does 0 fall in [4, 7)? No — so search the right half: low=4. Now low=4, high=6, mid=5, arr[5]=1. Is the left half (relative to this window) sorted? arr[4]=0 <= arr[5]=1, yes — that's the subarray [0, 1, 2]. Does 0 fall in [0, 1)? Yes — search left: high=4. Now low=4, high=4, mid=4, arr[4]=0 — found it, return 4. Still O(log n): every step halves the search space exactly like standard binary search, it just needs one extra check up front to figure out which half is safe to reason about.

Common mistakes

  • Running binary search on unsorted data. No crash, no warning — just silently wrong answers, which is precisely what makes this bug dangerous rather than merely annoying.
  • Off-by-one errors in low/high/mid bounds, especially using < instead of <= in the loop condition, or forgetting to update low/high past mid (mid + 1 / mid - 1, not just mid) — both can cause an infinite loop or skip the target entirely.
  • Assuming (low + high) // 2 is universally safe. In Python it is (integers don't overflow), but in languages with fixed-size integers, low + high can overflow for very large arrays — low + (high - low) // 2 avoids that, and it's worth knowing even if you never hit it in Python.
  • Reaching for binary search on a data structure without O(1) random access, like a linked list. Finding "the middle" of a linked list costs O(n) by itself, which erases the entire benefit of the technique.