Linear and binary search

Why it exists

Almost every program needs to find things: a record by its key, a word in a dictionary, a value in a table. How fast this can be done depends on what is known about the collection. If nothing is known, every element may have to be looked at. If the elements are sorted and can be reached by position, each look can throw away half of what remains, and a million elements need only 20 looks. This page shows both ends, and the reason the second needs two assumptions (order and direct access), which is what exam questions test.

Prerequisites

You need to count the steps of a loop (analysing loops) and to know that an array gives direct access to any position (arrays).

Precise definitions

Search problem. Given a collection $a_0, \ldots, a_{n-1}$ and a key $x$, report a position $i$ with $a_i = x$, or report that there is none. A search is successful if the key is present and unsuccessful otherwise.

Linear (sequential) search. Examine $a_0, a_1, \ldots$ in order until the key is found or the end is reached. It needs no assumption about the collection and works on arrays and on linked lists.

Binary search. For an array sorted in increasing order, keep a range $a_{lo}, \ldots, a_{hi}$ that contains every position where the key could still be. Examine the middle element $a_{mid}$; if it equals the key, stop; if it is smaller than the key, the key can only be to the right, so set $lo = mid + 1$; otherwise set $hi = mid - 1$. Stop when the range is empty.

Invariant. If the key is in the array at all, its position is in $[lo, hi]$. It is true at the start ($lo = 0$, $hi = n - 1$), each step keeps it true (because the array is sorted), and when the loop ends with $lo > hi$ the range is empty, so the key is absent. The range at least halves each time, which is why the loop ends.

Probe. One examination of an array element. Binary search makes one probe per iteration. The C code below uses two tests per probe (== and <), but they are one three-way comparison of the key with $a_{mid}$ (less, equal, greater). Exam questions count either probes or three-way comparisons, which are the same number; if a question counts every == and < separately it will say so.

Costs. For linear search the best case is $1$ probe, the worst case is $n$, and for a successful search with the key equally likely at each position the average is $(n+1)/2$. For binary search the best case is $1$ and the worst case is $\lfloor \log_2 n \rfloor + 1$ probes (equivalently $\lceil \log_2 (n + 1) \rceil$).

How it works

Both searches in C. They are the code that produced the numbers below; probes counts the array elements examined.

#include <stdio.h>
 
/* both return the index of key or -1; *probes receives the number of array elements examined */
static int linear_search(const int a[], int n, int key, int *probes) {
    *probes = 0;
    for (int i = 0; i < n; i++) {
        (*probes)++;
        if (a[i] == key) return i;
    }
    return -1;
}
 
static int binary_search(const int a[], int n, int key, int *probes) {
    int lo = 0, hi = n - 1;
    *probes = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        (*probes)++;
        if (a[mid] == key) return mid;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}
 
int main(void) {
    int sizes[] = {1, 3, 7, 8, 15, 16, 100, 1000};
    static int a[1000];
    printf("%5s %9s %9s %7s %9s %7s %6s\n", "n", "lin-hit", "bin-hit", "bin-max", "bin-miss", "miss-max", "bound");
    for (int s = 0; s < 8; s++) {
        int n = sizes[s], p;
        long lin_hit = 0, bin_hit = 0, bin_miss = 0;
        int hit_max = 0, miss_max = 0;
        for (int i = 0; i < n; i++) a[i] = 2 * i;            /* the keys are 0, 2, 4, ... */
        for (int i = 0; i < n; i++) {                        /* every successful search, once */
            linear_search(a, n, 2 * i, &p);
            lin_hit += p;
            binary_search(a, n, 2 * i, &p);
            bin_hit += p;
            if (p > hit_max) hit_max = p;
        }
        for (int g = 0; g <= n; g++) {                       /* every unsuccessful search: -1, 1, 3, ..., 2n - 1 */
            binary_search(a, n, 2 * g - 1, &p);
            bin_miss += p;
            if (p > miss_max) miss_max = p;
        }
        int bound = 0;
        for (int m = n; m > 0; m /= 2) bound++;              /* floor(log2 n) + 1 */
        printf("%5d %9ld %9ld %7d %9ld %7d %6d\n", n, lin_hit, bin_hit, hit_max, bin_miss, miss_max, bound);
    }
    return 0;
}

    n   lin-hit   bin-hit bin-max  bin-miss miss-max  bound
    1         1         1       1         2       1      1
    3         6         5       2         8       2      2
    7        28        17       3        24       3      3
    8        36        21       4        29       4      4
   15       120        49       4        64       4      4
   16       136        54       5        70       5      5
  100      5050       580       7       680       7      7
 1000    500500      8987      10      9987      10     10

Read the columns for each $n$ (the keys are $0, 2, 4, \ldots$, so every odd number is an unsuccessful search):

• lin-hit is the total number of probes of linear search over all $n$ successful searches: $1 + 2 + \cdots + n = n(n+1)/2$, so the average is $(n+1)/2$. An unsuccessful linear search always examines all $n$ elements.
• bin-hit and bin-miss are the totals of binary search over all $n$ successful and all $n + 1$ unsuccessful searches. For $n = 1000$ a successful search takes $8987/1000 \approx 9$ probes on average.
• bin-max and miss-max are the worst cases, and bound is $\lfloor \log_2 n \rfloor + 1$. They agree in every row, for present and for absent keys.

The animation. The code is binary_search from the page, run for real: faded positions are ruled out. The first search finds 47 in four probes (positions 7, 11, 9, 10); the second search, for 30, ends when $lo$ passes $hi$ after four probes.

Why $\lfloor \log_2 n \rfloor + 1$. After $k$ probes at most $n/2^k$ positions remain (rounded down), so the range is empty after at most $\lfloor \log_2 n \rfloor + 1$ probes. More exactly, a range of size $m$ becomes a range of size at most $\lfloor m/2 \rfloor$, and $\lfloor m/2 \rfloor = 0$ only after the size has been halved $\lfloor \log_2 m \rfloor + 1$ times. The recurrence of the running time is $T(n) = T(n/2) + 1$, which gives $\Theta(\log n)$ (Master theorem, case 2).

Binary search is optimal. Any algorithm that searches a sorted array by comparing the key with elements must be able to answer "present at position $i$" for each of the $n$ positions, and it can only do so after it has compared the key with $a_i$. So its decision tree has at least $n$ internal nodes, one per key, and each node has at most two continuing branches (less and greater). A binary tree with $n$ nodes has a path of at least $\lceil \log_2 (n + 1) \rceil$ nodes, so some search needs that many comparisons, which is exactly the worst case of binary search.

Why the loop condition and the updates matter. The updates must be lo = mid + 1 and hi = mid - 1, because $a_{mid}$ has just been examined and excluded. An update lo = mid can loop forever: with $lo = 3$ and $hi = 4$ the middle is $3$ and nothing changes.

The midpoint. The expression (lo + hi) / 2 adds two valid indices; if their sum exceeds the largest int the addition overflows (undefined behaviour for signed integers in C). The expression lo + (hi - lo) / 2 never leaves the range between $lo$ and $hi$. The program below uses 64-bit arithmetic to show the true numbers without invoking undefined behaviour.

#include <stdio.h>
#include <limits.h>
 
int main(void) {
    long long lo = 1500000000, hi = 1600000000;     /* two valid indices of a huge array */
    printf("INT_MAX          = %d\n", INT_MAX);
    printf("lo + hi          = %lld\n", lo + hi);
    printf("fits in an int   = %s\n", lo + hi <= INT_MAX ? "yes" : "no");
    printf("lo + (hi - lo)/2 = %lld\n", lo + (hi - lo) / 2);
    return 0;
}

INT_MAX          = 2147483647
lo + hi          = 3100000000
fits in an int   = no
lo + (hi - lo)/2 = 1550000000

First occurrence. With duplicates, plain binary search returns some matching position. To find the first one (the lower bound, the first position whose element is not smaller than the key) keep the half-open range $[lo, hi)$ and never stop early:

/* a[0..n-1] is sorted; returns the first position whose element is not smaller than key (n if there is none) */
int lower_bound(const int a[], int n, int key) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

The result is the first position of the key if it is present, and otherwise the position where the key would have to be inserted to keep the array sorted. For the 15-key array of the animation, lower_bound of 30 is $7$, which is where $31$ stands.

What binary search needs. Two things at once. Order: without it, discarding half is wrong. Direct access: finding the middle element must cost $O(1)$. On a sorted linked list reaching the middle costs $n/2$ steps, then $n/4$, and so on, in total $\Theta(n)$: binary search on a linked list is no better than linear search. On a sorted array with many insertions, keeping the order costs $\Theta(n)$ shifts per insertion, which is why other structures (balanced search trees, hash tables) are used for dynamic sets.

Outside the syllabus. If the keys are spread evenly, interpolation search guesses the position from the key's value and takes expected $O(\log \log n)$ probes, but its worst case is $\Theta(n)$.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Binary search is the simplest divide and conquer algorithm: one subproblem of half the size and constant work, see divide and conquer; its recurrence is solved in solving recurrences. A binary search tree makes the same decisions with pointers instead of indices (binary search trees), and a hash table trades order for expected constant time.

PYQs

Consider the following array:
23 , 32 , 45 , 69 , 72 , 73 , 89 , 97
Which algorithm out of the following options uses
the least number of comparisons (among the array
elements) to sort the above array in ascending
order?

Given an integer array of size N, we want to check
if the array is sorted (in either ascending or
descending order). An algorithm solves this
problem by making a single pass through the array
and comparing each element of the array only with
its adjacent elements. The worst-case time
complexity of this algorithm is

What is the worst-case number of arithmetic
operations performed by recursive binary search
on a sorted array of size n

Let A be an array of 31 numbers consisting of
sequence of 0's followed by a sequence of 1's. The
problem is to find the smallest index i that A[i] is 1
by probing the minimum numbers of locations in A.
The worst case number of probes performed by an
optimal algorithm is   .

Match the algorithms with their time complexities:
Algorithm
Time
complexity
P Towers of Hanoi with
n disks
i
Θ(n2 )
Q Binary search given n
sorted numbers
ii
Θ(nlog n)
R Heap sort given n
numbers at the worst
case
iii
Θ(2n )
S
Addition of two n × n
matrices
iv
Θ(logn)
ALGORITHMS

Check Out Our Gate Courses & Secure Your Dream Rank !

An unordered list contains n distinct elements. The
number of comparisons to find an element in this list
that is neither maximum nor minimum is :

Consider the C function given below. Assume that
the array listA contains n(>0) elements, sorted in
ascending order
int ProcessArray(int *listA, int x, int n)
{
int i, j, k;
i = 0;
j = n-1;
do {
k = (i+j)/2;
if (x <= listA[k]) j = k-1;
if (listA[k] <= x) i = k+1;
}
while (i <= j);
if (listA[k] == x) return(k);
else return -1;
}
Which one of the following statements about the
function ProcessArray is CORRECT?

Self-check

Revision card

References