Binary Search

Problem statement

Let aᵢ, 1 ≤ i ≤ n, be a list of elements stored in non-decreasing order. Determine whether a given element x is present in the list. If x is present, find a value j such that aⱼ = x. If x is not in the list, j is set to zero.

Divide-and-conquer strategy

Let Small(P) be true if n = 1. If P has more than one element, divide P into new subproblems as follows.

Let a(l : h) be the list of elements. Pick an index q, l ≤ q ≤ h, and compare x with a_q. Three possibilities can occur:

1. x = a_q      – P is immediately solved.
2. x < a_q      – x has to be searched only in the sublist al, al+1, …, aq−1. So P reduces to a(l : q−1).
3. x > a_q      – x has to be searched only in the sublist aq+1, aq+2, …, ah. So P reduces to a(q+1 : h).

low = 0 at the left end and high = n−1 at the right end. If key < A[mid], search the left side. If key > A[mid], search the right part.

Recursive binary search

It is initially invoked as BinSrch(a, l, h, x).

Algorithm BinSrch(a, l, h, x)
/* Given an array a[l:h] of elements in nondecreasing order,
   1 ≤ l ≤ h, determine whether x is present, and if so,
   return j such that x = a[j]; else return 0. */
{
    if (h = l) then            // If Small(P)
    {
        if (x = a[l]) then return l;
        else return 0;
    }
    else
    {   // Reduce P into smaller subproblems.
        mid := ⌊(l + h) / 2⌋;
        if (x = a[mid]) then return mid;
        else if (x < a[mid]) then
            return BinSrch(a, l, mid - 1, x);
        else
            return BinSrch(a, mid + 1, h, x);
    }
}

Iterative binary search

Algorithm BinSrch(a, n, x)
/* Given an array a[1:n] of elements in nondecreasing order,
   n ≥ 0, determine whether x is present, and if so, return j
   such that x = a[j]; else return 0. */
{
    low := 1; high := n;
    while (low ≤ high) do
    {
        mid := ⌊(low + high) / 2⌋;
        if (x < a[mid]) then
            high := mid - 1;
        else if (x > a[mid]) then
            low := mid + 1;
        else return mid;
    }
    return 0;
}

Example

Let the array consist of 14 elements:

Analysis of comparisons

The comparison is between x and an element of a[ ]. Assume only one comparison is needed to decide which of the three possibilities of the if statement holds.

The number of element comparisons needed to find each of the 14 elements:

Successful search

Average number of comparisons = (3 + 4 + 2 + … + 4) / 14 = 45 / 14 ≈ 3.21

Unsuccessful search

There are 15 possible positions at which an unsuccessful search can terminate. If x < a[1], the algorithm needs 3 element comparisons to determine unsuccessfulness. For all the remaining possibilities, it needs 4 element comparisons.

Average number of comparisons = (3 + 14 × 4) / 15 = 59 / 15 ≈ 3.93

Binary decision tree for n = 14

The diagram shows the internal nodes only. The external (square) nodes hang below the circles wherever a node has a missing child.

The first comparison of x is with a[7]. If x < a[7], it is compared with a[3], and so on. If the search is successful, the algorithm ends at one of the circular nodes (internal nodes). If the search is unsuccessful, the algorithm terminates at one of the square nodes (external nodes).

If n is in the range [2^k−1, 2^k), then BinSearch makes at most k element comparisons for a successful search, and either k−1 or k comparisons for an unsuccessful search.

Time complexity

It is based on the height of the binary decision tree.

Worst case

Every time, one comparison is made and the given n numbers are divided into n/2. The recurrence relation is:

T(n) = 1               if n = 1
     = T(n/2) + 1      otherwise

T(n) = T(n/2) + 1
     = [T(n/4) + 1] + 1
     = [T(n/8) + 1] + 2
     = T(n/2³) + 3
       ⋮
     = T(n/2ᵏ) + k

Let n = 2^k ⇒ k = log₂n. Then:

T(n) = T(1) + log₂n
     = 1 + log₂n

∴ T(n) = O(log₂ n)