Searching — Linear Search and Binary Search

Linear search

Scan elements one by one until the key is found.

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

$O(n)$, works on unsorted data and on any sequential structure (linked lists, streams). For a key present with probability $p$ at a uniform position: expected comparisons $p\frac{n+1}{2} + (1-p)n$.

Sentinel trick: append the key at the end so the loop needs no bounds check (halves comparisons in low-level code).

Binary search

On a sorted array, compare the key with the middle element and discard the half that cannot contain it.

def binary_search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:                 # invariant: if x is in a, it is in a[lo..hi]
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        elif a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1                       # lo is now the insertion point

def binary_search_rec(a, x, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if a[mid] == x:
        return mid
    if a[mid] < x:
        return binary_search_rec(a, x, mid + 1, hi)
    return binary_search_rec(a, x, lo, mid - 1)

Cost

$T(n) = T(n/2) + O(1) = O(\log n)$. Worst-case number of three-way comparisons: $\lfloor\log_2 n\rfloor + 1$ (10 for $n = 1000$, 20 for $n = 10^6$). The comparisons trace a path in a balanced binary decision tree of height $\lfloor\log_2 n\rfloor$.

Variants

Python's bisect module: bisect_left(a, x) (first index with a[i] >= x), bisect_right(a, x) (first index with a[i] > x), insort(a, x) (insert in order; $O(n)$ because of shifting).

Binary search on the answer

If a predicate $P(v)$ is monotone (false … false, true … true), binary search finds the boundary in $O(\log(\text{range}))$ evaluations: integer square roots, minimum capacity to ship packages in $D$ days, smallest threshold achieving a target, root-finding by bisection on a continuous function.

Sort first, or search repeatedly?

One search: linear search, $O(n)$. Many searches ($k$ of them): sort once in $O(n\log n)$, then $O(\log n)$ each, total $O((n + k)\log n)$ — or build a hash set for $O(1)$ expected lookups if you only need membership (see hash tables).

Quick revision