Binary Search

By Riolku
Written 27 days ago

Binary search is one of the most well-known and fundamental algorithms in computer science. It is also something that many people do without thinking about it on a day to day basis!

Here's an example. Lets say that you are searching through a dictionary, looking for the word 'search'. First you open the book and find the word 'binary'. Immediately, you know that 'search' is farther along than your current page, and you can immediately rule out the previous pages.

Why is this?

The answer is because the dictionary is sorted alphabetically. If we find a word that is smaller than the sought word, we know to look later in the book. On the other hand, if we had found 'tech', we would know that 'search' is before it.

This has fantastic applications in computer science. Let's consider an array of size N, with 16 elements, like so:

[1, 2, 4, 5, 7, 10, 14, 15, 17, 20, 24, 27, 30, 31, 32, 34]

Let's say that we are searching for the number \( 4 \). First, we try the halfway mark, which is \( 15 \). We know that \( 4 < 15 \), so we start searching on the left of 15. The full process to find \( 4 \) is as follows:

15, 5, 2, 4

This yields a very easy recursive algorithm, which we show in python below:

def binary_search(arr, elem):
  if len(arr) == 0:
    # the element does not exist in the array
    return -1

  mid = len(arr) // 2

  if arr[mid] == elem:
    return mid

  # must be on the right
  if arr[mid] < elem:
    return binary_search(arr[mid + 1:], elem)
  # otherwise, its on the left
  return binary_search(arr[:mid], elem)

Some of you might notice that there is also an iterative way of doing this, which is also shown here:

def binary_search(arr, elem):
  # keep track of top and bottom of searched range
  lo = 0
  hi = len(arr) - 1

  while lo <= hi:
    mid = (lo + hi) // 2
    if arr[mid] == elem:
      return mid

    if arr[mid] < elem:
      # set the left bound to mid + 1
      lo = mid + 1

      hi = mid - 1
  # Not in array!
  return -1

It is very important to note that this technique works solely on things that are sorted.

Note that although it is crucial to understand how to implement an algorithm such as binary search, it is also important to recognize that python has a library for this, namely, bisect. C++ also has these functions in <algorithm>.

Finally, we analyze the time complexity of binary search. Since we cut the search area in half every time, the time complexity is the number \( x \) such that \( 2^x = N \). This number is \( \text{log}_2 N \).

Therefore, the complexity of binary search is \( \mathcal O(\text{log }N) \)