Binary Search

Suppose that table entries are stored in an array in alphabetical order by key, similarly to the way a telephone book is in alphabetical order. You want to find a particular key k in the array. One approach is to look in the middle of the array. Suppose that you find key m there. If k = m then you are done, since you have found what you are looking for. If k comes before m in alphabetical order then key k must be in the first half of the array, if it is in the array at all. If k comes after m in alphabetical order then key k must be in the second half of the array, if it is in the array at all. That leads to the following function definition.

  // lookup(x,A,lo,hi) returns the string associated with key
  // x in the section of array A from index lo to index hi.  If x is not
  // a key in that section of A, then lookup returns NULL.

  const char* lookup(const char* x, const TableEntry A[], int lo, int hi)
  {
    if(lo > hi)
    {
      return NULL;
    }
    else 
    {
      int mid = (lo + hi)/2;
      int cmp = strcmp(A[mid].key, x);
      if(cmp == 0)
      {
        return A[mid].value;
      }
      else if(cmp < 0)
      {
        return lookup(x, A, lo, mid-1);
      }
      else
      {
        return lookup(x, A, mid+1, hi);
      }
    }
  }

How much time does it take to look up a key in a table that has n entries using binary search? Each time you look at an entry, either you finish or the next call has only about half as many entries to search. We have seen that if you start at n and successively perform halving steps, then the number of steps that you perform before the result is 1 is about log₂(n). So the time to perform binary search on an array of size n is O(log₂(n)).