The binary search algorithm is a classic algorithm that lets us find an item in a sorted array in O(log n) time complexity. In this post, we’ll review how the algorithm works and learn how to implement it in Javascript.

A conceptual example

Binary search works by continuously dividing an array in half and looking at the middle number until you find a match (or no match is found). Let’s say we have the array [2, 3, 4, 6, 7, 9, 10] and we’re asked to find the index of the number 7.

In binary search, we first identify the middle item in the array and compare that to the number we’re looking for. We can find the middle index by adding the index of the start of the array (0) to the index of the end of the array (6) and divide by 2. In other words, middle = (start + end) / 2 = (6 + 0) / 2 = 3.

The number at index 3 is 6. We compare this to the number we’re looking for, 7. Since 6 is less than 7, we now know that all items to the left of (and including) 6 are less than the number we’re looking for (this is why it’s critical the array is sorted).

Since all those numbers are ruled out, we can now think of it as a new array, with the start position being one to the right of the previous middle position and the end still being at the end of the array.

We calculate the middle index the same way: middle = (start + end) / 2 = (4 + 6) / 2 = 5. The number at the new middle index is 9, which is now greater than 7. We therefore know that all of the items to the right of (and including) 9 are greater than the number we’re looking for.

We repeat the process and create a new sub-array, but this time our end moves to the left of 5th index. At this point, our start and end index both 4, which means our middle index is calculated as: middle = (4 + 4) / 2 = 4.

We now find that this number is the one we’re looking for! We therefore return the index 4 from our algorithm.

Implementing this algorithm in JavaScript

Generally, a binary search function will receive two inputs: the sorted array and the target number. Usually, the goal of the function is to either output the index of the target value, or the number -1 if the target value is not found.

function binarySearch(array, target) {
  // TBD
}

Looking at our conceptual review above, we can see that there is a start and end value that moves throughout the algorithm. Therefore, we can initialize these values using let, assuming they will change:

function binarySearch(array, target) {
  let start = 0;
  let end = array.length - 1;
}

Next, we implement a loop that will keep cutting the array in half until the right index is found. The loop can’t be infinite, so we need to think about when it should terminate. We see in our conceptual example that we can end up in a situation where the start index is equal to the end index, and that’s okay. What we’ can’t have is a start index that is greater than the end index… that’s how we know we’ve gone too far:

function binarySearch(array, target) {
  let start = 0;
  let end = array.length - 1;
  while (start <= end) {
    // TBD
  }
  // If we got this far, we never found the target
  return -1;
}

Note that if we get to the point that the start index is greater than the end index, we have exhausted all the items in the array and the target simply doesn’t exist, so we return -1.

Finally, we can implement the core logic of the algorithm:

• Finding the middle item
• If the middle item equals the target, return the index (we found it!)
• If the middle item is less than the target, move the start index to the right of the middle item
• If the middle item is greater than the target, move the end index to the left of the middle item

function binarySearch(array, target) {
  let start = 0;
  let end = array.length - 1;
  while (start <= end) {
    // Find the middle index
    const middle = Math.floor((start + end) / 2);
    if (array[middle] === target) {
      return middle;
    } else if (array[middle] < target) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }
  }
  // If we got this far, we never found the target
  return -1;
}

You may have noticed that I’m using Math.floor to compute the middle index. This is because arrays with an even number of items have no true middle item, so we want to make sure we have an integer index rather than something like 2.5.

Computing the time complexity

I mentioned above that the time complexity of this algorithm is O(log n). This can be computed by considering how many times you might have to divide an arbitrary list length (n) by 2 until you just have one item left. So our equation is as follows, where we’re solving for x.

1 = n / (2^x)
2^x = n
log(2^x) = log(n)
x * log(2) = log(n)
x = log(n)

And thus we have implemented the binary search algorithm in JavaScript and derived its time complexity.