Problem

Given a sorted sequence, find the exact position of a given element.

A simple approach is to do a linear search (check each element one by one). The time complexity of a linear search is O(n). Another approach to perform the same task in O(log n) is using Binary Search.

Considering a list that contains 1 million items:
- If we perform a linear search we could have to make 1 million iterations and 1 million comparisons
- With a binary search we will find it for sure with no more than 20 iterations and 20 comparisons (symptotically 5000 times faster!)

Applications

  • Find data index, more importantly within huge sequences database).
  • Key idea in binary search trees, a very important data structure.
  • Used to esitmate the square roots of numbers (e.g. Newton's method).

Homonyms

  • Dichotomic search
  • Half-interval search
  • Logarithmic search
  • Binary chop

Binary search is a decrease and conquer search algorithm than can be used on a sorted array. It operates by determining whether the search value is less or greater than the middle value. It then loop on the lower or upper half of the sequence until either the value is found or not (half is an empty sequence).

Steps

  • 1. Compare search value with the middle element.
  • 2. If they match, we are done: return the middle index.
  • 3. If the search value is bigger: loop within the upper half sequence.
  • 4. If the search value is smaller: loop within the lower half sequence.

Pseudo-Code

Index BinarySearch(Iterator begin, Iterator end, const T key)
{
  auto index = -1;
  auto middle = begin + distance(begin, end) / 2;

  // While there is still objects between the two iterators and no object has been foud yet
  while(begin < end && index < 0)
  {
    if (IsEqual(key, middle))   // Object Found: Retrieve index
      index = position(middle);
    else if (key > middle)      // Search key within upper sequence
      begin = middle + 1;
    else                        // Search key within lower sequence
      end = middle;

    middle = begin + distance(begin, end) / 2;
  }

  return index;
} 

As the analysis visualization is quite trivial: it has been included within the header image carousel of this article.

Time

Best

The best configuration occurs when the first middle point selected is the search value; leading to a complexity of O(1).

Average / Worst

The worst case scenario occurs when the search value is not in the sequence.
After the first look-up, we loop the search on the lower/upper half and so on. Let's put this into a recurrence relation: $$T(n) = O(1) + T(\frac{n}{2})$$ Using the master theorem for divide-and-conquer recurrences: T(n) = O(log n).

Space

Binary search does not use any buffer nor does make any recursion. Thus, it requires O(1) space in all case.