A Guide to Understanding Binary Search

In working with collections (lists, queues, maps) of data, we usually have to perform one or more of the following operations on the collection: accessing, searching, appending, inserting, replacing/swapping, deleting and sorting

Binary search is one of the most popular algorithms for searching for a number within a sorted list of numbers. It has a time complexity of O(log N) which means that its ability to find a number in a sorted list is minimally affected by the length of numbers in the list.

Binary Search - Analogy

The binary search algorithm is similar to how we search through a numbered book to get to a page. First, we open up to a random page. If the page number is greater than that of the page we are looking for, we move left, else, we move to the right. We repeat this procedure until we find the page number we are looking for.

Two things stand out

the page numbers are sorted so we can know to search left or search right
the number of pages is finite (has a definite end)

In binary search, we ask the computer to do something similar - start from a midpoint in the collection, evaluate if the the midpoint number is greater than or less than the number being searched for and search forward or backward based on the result of the evaluation until the number is found.

The algorithm is generally called Divide and Conquer because each time it does not find what it is searching for in a comparison, it focuses on one half of the collection, ignoring the other half; dividing the items by half after each evaluation.

Binary Search - Pseudocode

Situations requiring binary search are usually worded in the following manner:

Given a list of numbers sorted in ascending order, find out if the number x exists in the list. If it does, return the index where it was found, otherwise, return -1.

How do we go about this?

1. Handle Edge Cases

It is possible that the list contains only one number. If it does, it would be efficient to exit early. To do that, we check if that single number is the number we are looking for (x). If it is, we return the index of the number (usually 0), else, we return -1.

if (list.length == 1 and list[0] != x) return -1
if (list.length == 1 and list[0] == x) return 0

2. Establish Boundaries

Having handled that edge case, we can move on to searching through lists that have more than one number. To do this, we want to first establish the bounds within which we can search.

We cannot go beyond the last item in the list found at list[list.length - 1] and the first item in the list found at list[0]. With that, we have our lower index bound and our upper index bound.

lowerIndex = 0;
upperIndex = list.length - 1;

3. Search

We begin to search through the list the way we would search for a page in a book. Let us see this as searching for page number x in a book.

In searching through a book, we open to a random page at first. For binary search, we access the item at the middle of the list at first. How do we get to the middle of the list?

midIndex = round_down((upperIndex + lowerIndex) / 2)

The sum of the boundaries divided by two and then rounded down is the middle index of the list. It is rounded down so that the upper bound is not overstepped. Overstepping the upper bound can lead to accessing an index higher than the maximum index of the list, and that would cause an index out of range error.

The operations we repeat in this search start from accessing a page. We would need a loop to perform operations repeatedly. The condition which will terminate the loop will be discussed soon.

...
while (condition to terminate the loop) {
  // accessing a middle index value
  midIndex = round_down((upperIndex + lowerIndex)/2)
  midVal = list[midIndex]
}

4. Compare Values

midVal gives us the number at midIndex. With midVal, we can determine if we should search towards the left of the list, towards the right or exit because x has been found.

...
while (condition to terminate the loop) {
  midIndex = round_down((upper + lower)/2)
  midVal = list[midIndex]

  if (x == midVal) {
    return midIndex // (1)
  }

  if (x > midVal) {
    lower = midIndex + 1 // (2)
  }

  if (x < midVal) {
    upper = midIndex - 1 // (3)
  }
}

If x is midVal, we have found what we are looking for. We can return (1).

If x is greater than midVal, then the value we are looking for is towards the right. We have to increase the next value of round_down((upperIndex + lowerIndex)/2) (also known as midIndex) in the next loop so that it can point further to the right.

In trying to achieve this, we cannot increase upperIndex because it is the upper bound and it should not exceed the maximum list index. We can increase lower though. We set it to midIndex + 1 because the value we are looking for is beyond midIndex. (2)

If x is less than midVal, then the value we are looking for is on the left of the list. We have to reduce the next value of midIndex (in the next loop) so that it can point leftwards.

In doing this, either lowerIndex or upperIndex must be reduced. We cannot reduce lowerIndex because we may end up reducing it to below 0 and then have an index out of range error because lowerIndex may become less than 0. What we do is to reduce upperIndex by 1. (3)

5. Exit the loop

For each run of the loop where we did not find x, it is either lowerIndex is increased, tending towards upperIndex, or the upperIndex is reduced, tending towards lowerIndex. We know that all hope is lost when lowerIndex becomes higher than upperIndex because it shouldn’t. The condition to keep running the loop is then while (lowerIndex <= upperIndex).

while (lower <= upper) {
  midIndex = round_down((upperIndex + lowerIndex)/2)
  midVal = list[midIndex]

  if (x == midVal) {
    return midIndex // (1)
  }

  if (x > midVal) {
    lower = midIndex + 1 // (2)
  }

  if (x < midVal) {
    upper = midIndex - 1 // (3)
  }
}

Binary Search - JavaScript

Here’s a JavaScript implementation of binary search

/**
* @param {number[]} list the list of numbers sorted in ascending order
* @param {number} x the number for the index we are searching for
*/
function findIndex(list, x) {
  if (list.length == 1 && list[0] == x) return 0
  if (list.length == 1 && list[0] != x) return -1

  let lowerIndex = 0
  let upperIndex = list.length - 1

  while(lowerIndex <= upperIndex) {
    midIndex = Math.floor((lowerIndex + upperIndex)/2)
    midValue = list[midIndex]

    if (midValue == x) {
      return midIndex
    }

    if (midValue > x) {
      lowerIndex = midIndex + 1
    }

    if (midValue < x) {
      upperIndex = midIndex - 1
    }
  }

  return -1
}

Binary Search - Golang

Here’s an implementation of binary search in Golang

func findIndex(list []int, x int) int {
  if len(list) == 0 && list[0] == x {
    return 0
  }

  if len(list) == 0 && list[0] != x {
    return - 1
  }

  lowerIndex := 0
  upperIndex := len(list) - 1

  for lowerIndex <= upperIndex {
    midIndex := (lowerIndex + upperIndex)/2
    midValue = list[midIndex]

    if midValue == x {
      return midIndex
    }

    if midValue > x {
      lowerIndex = midValue + 1
    }

    if midValue < x {
      upperIndex = midValue - 1
    }
  }

  return -1
}

Conclusion

It’s great to have you still reading at this point. It suggests that you have gone through the article. Here are a couple of things you may want to try for practice.

How do you update the algorithm to fit situations where the numbers in the list are in descending order?
How do you update the algorithm to fit situations where there are no numbers in the list, but objects such as person.age and you have to find the person with a certain age x
Can you try Question 278 on LeetCode?

Binary Search - Analogy#

Binary Search - Pseudocode#

1. Handle Edge Cases#

2. Establish Boundaries#

3. Search#

4. Compare Values#

5. Exit the loop#

Binary Search - JavaScript#

Binary Search - Golang#

Conclusion#