Search algorithms: linear, binary, interpolation

Finding a student number in a list, looking up a word in a dictionary, finding a product in a price list: all are search problems. There are two basic strategies. Linear search looks one by one from start to end; it works on any array but is slow. Binary search works only on a sorted array but is incredibly fast: at most 20 steps for a million elements. The exam asks for the low/mid/high trace table of binary search, the number of comparisons, and small mistakes in the code.

Golden rules:

1. Binary search works only on a sorted array.
2. The loop condition is low <= high. A one-element range is checked too.
3. When moving the bound, mid + 1 and mid - 1.
4. In the worst case $\lfloor \log_2 n \rfloor + 1$ comparisons.

Linear search (linear / sequential search)

static int linearSearch(int[] a, int x) {
    for (int i = 0; i < a.length; i++)
        if (a[i] == x) return i;
    return -1;
}

All are O(n). Advantage: it doesn’t require sorting, and it works on a linked list too. Even if the array is sorted, linear search doesn’t use that; for a value that isn’t there it always goes to the end (in a sorted list you can add an early exit, week 3).

Binary search

When you look up a word in a dictionary you open in the middle. If the word you are looking for comes before that page, you discard the right half entirely. At each step the search space is halved.

static int binarySearch(int[] a, int x) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == x) return mid;
        else if (a[mid] < x) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

The trace table

The array (indices on top):

index:   0  1   2   3   4   5   6   7   8   9
value:   3  8  12  17  21  25  30  34  41  47

Searching for 47 (the rightmost element, one of the worst cases):

low=0 high=9 mid=4 a[mid]=21
low=5 high=9 mid=7 a[mid]=34
low=8 high=9 mid=8 a[mid]=41
low=9 high=9 mid=9 a[mid]=47
result 9 probes=4

Searching for 5 (not in the array):

low=0 high=9 mid=4 a[mid]=21
low=0 high=3 mid=1 a[mid]=8
low=0 high=0 mid=0 a[mid]=3
stop: low=1 high=0
result -1 probes=3

The loop ends when low > high. At that moment low is the position where the searched value can be inserted without breaking the order (5 should go to index 1). When it doesn’t find it, Java’s ready-made Arrays.binarySearch returns -(low) - 1: −2 in this example.

TIP · Trace table layout. On the exam, write low | high | mid | a[mid] | comparison result on each line. When computing mid, don’t forget integer division: (0 + 9) / 2 = 4, not 4.5.

How many comparisons?

Each probe halves the range. Going from n elements down to 1 element needs $\log_2 n$ halvings, plus 1 to check the last element. The worst case is $\lfloor \log_2 n \rfloor + 1$:

n=10 worst probes=4 floor(log2 n)+1=4
n=100 worst probes=7 floor(log2 n)+1=7
n=1000 worst probes=10 floor(log2 n)+1=10
n=1000000 worst probes=20 floor(log2 n)+1=20

The cost: the array must be sorted. Sorting takes O(n log n) at best (week 14). Sorting isn’t worth it for a single search; it is worth it if many searches will be made on the same array.

The recursive form

static int binarySearch(int[] a, int x, int low, int high) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (a[mid] == x) return mid;
    if (a[mid] < x) return binarySearch(a, x, mid + 1, high);
    return binarySearch(a, x, low, mid - 1);
}

The recurrence is $T(n) = T(n/2) + 1$, with solution O(log n) (week 11). The loop version uses O(1), and the recursive version uses O(log n) extra stack memory.

Three classic mistakes

1. while (low < high). When the range shrinks to a single element, the loop ends without looking at that element. On {1, 3, 5}:

find 1 -> -1  find 3 -> 1  find 5 -> -1  

2. low = mid or high = mid. When low = 3, high = 4, mid = 3; if you write low = mid, low never changes: an infinite loop.

3. Overflow of (low + high) / 2.

int low = 1_500_000_000, high = 2_000_000_000;
System.out.println((low + high) / 2 + " vs " + (low + (high - low) / 2));

-397483648 vs 1750000000

This bug stayed in Java’s own library for years. It shows up with very large arrays; on the exam you are expected to write the correct formula.

PITFALL · Binary search on an unsorted array. It gives no error, it silently returns a wrong result. On {9, 2, 7, 4, 1, 8, 3}, 2 and 8 are found by luck but 7 is not found (−1), because the algorithm discards the left half where 7 is in the first step.

Duplicate values

On {2, 4, 4, 4, 7} standard binary search returns index 2 for 4, because the first mid is there. If you want the first position, don’t stop at a match: record the result and keep searching on the left with high = mid - 1. This variation returns index 1. For the last position, symmetrically low = mid + 1.

Interpolation search

When you look for “Yılmaz” in a phone book, you open not in the middle but near the end. Interpolation search does the same: it estimates the position of the target by looking at its value.

$pos = low + \frac{(x - a[low]) \cdot (high - low)}{a[high] - a[low]}$

Then, as in binary search, it compares with a[pos] and moves low or high.

low=0 high=9 pos=6 a[pos]=70
6 probes=1
8 probes(skewed)=9
8 probes(binary)=3

The first two lines: in the array {10, 20, ..., 100}, 70 was found on the first estimate. The last two lines: in a skewed array like {1, 2, ..., 9, 1000}, searching for 9 took 9 probes with interpolation and 3 probes with binary search. The value 1000 keeps shifting the estimate to the left.

Common mistakes

static int binarySearch(int[] a, int x) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == x) return mid;
        else if (a[mid] < x) low = mid + 1;   // right half
        else high = mid - 1;                  // left half
    }
    return -1;
}

static int binarySearch(int[] a, int x, int low, int high) {
    if (low > high) return -1;                       // empty range
    int mid = low + (high - low) / 2;
    if (a[mid] == x) return mid;
    if (a[mid] < x) return binarySearch(a, x, mid + 1, high);
    return binarySearch(a, x, low, mid - 1);
}

int low = 0, high = a.length - 1;
while (low < high) {
    int mid = (low + high) / 2;
    if (a[mid] == x) return mid;
    else if (a[mid] < x) low = mid + 1;
    else high = mid - 1;
}
return -1;

int low = 0, high = a.length - 1, ans = -1;
while (low <= high) {
    int mid = low + (high - low) / 2;
    if (a[mid] == x) { ans = mid; high = mid - 1; }
    else if (a[mid] < x) low = mid + 1;
    else high = mid - 1;
}
return ans;