4.3.4.1–4.3.4.3 - Linear, binary and binary-tree search (Python)

Linear search

Linear search checks items one at a time and can work even when the data is unordered.

Start at index 0. Compare the current item with the target; return its index if equal, otherwise advance. If the loop reaches the end, report not found. Returning only after all non-matches is essential: the first item being wrong does not mean later items are wrong.

def linear_search(values, target):
    for index in range(len(values)):
        if values[index] == target:
            return index
    return -1

For [14, 5, 22, 9] and target 22, the examined index/value pairs are (0,14), (1,5), (2,22), then return 2. For target 8, all four elements are examined and the function returns −1. An empty list needs zero comparisons and also returns −1. With duplicates this function returns the first matching index.

A worst-case linear search examines all n items, so it has $O(n)$ time. A successful first-item search is constant time, $O(1)$. When describing the specification's linear complexity, state that you mean the worst case. Average successful search is also linear under an equally likely target-position assumption.

Binary search on ordered data

Binary search discards roughly half the remaining positions after each midpoint comparison, so it requires ordered data.

For ascending data, maintain inclusive bounds low and high. Compute mid = (low + high) // 2. A match finishes. If the target is larger than the midpoint item, set low = mid + 1; otherwise set high = mid - 1. Excluding the already-tested midpoint guarantees progress. Stop unsuccessfully when low > high. In an empty list the initial bounds are 0 and −1, so the loop does not run.

For [3, 7, 11, 16, 20, 25, 31], target 25 gives:

The ordered property justifies excluding positions 0–3 after the first comparison. On an unordered list that deduction is invalid, even if the code terminates. A missing target 18 would next examine index 4, then cross the bounds and return −1.

Halving n positions until at most one remains takes about $\log_2 n$ halvings, giving $O(\log n)$ worst-case search time with direct access to midpoint items. Sorting a previously unordered list has its own cost; do not claim the whole sort-then-search operation costs only $O(\log n)$.