Binary search in JavaScript

The name binary comes from the technique the algorithm is based on. If we have an array of numbers ordered from smallest to greatest, we will keep dividing the array into two parts until we are left with just one element, the one we want to find.

This technique is more efficient that the brute force iteration, which we will look at in the following section.

Finding the element with iteration

Assume we have an array of the first few primes. If the numbers are not ordered yet, we will need to sort them first. For the sake of simplicity and because this post is about binary search, the numbers will already be sorted in the array:

const numbers = [2, 3, 5, 7, 11, 13, 17];

function findWithIteration(arr, element) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === element) return arr.indexOf(element);
  }

  return 'The value cannot be found in the array';
}

The function is very straightforward: Loop over the elements of the array until we get to element, which is the one we are looking for. In case we don’t find element in the array, we will return a simple message that the number cannot be found. If we call findWithIteration(numbers, 11) to find the index of 11, we will get 4, which is correct as 11 is the fifth element in the array.

Although this method works, it has some disadvantages, especially when we need to find an element in an array of several million elements. Iteration is expensive in terms of time needed to perform the task and we can do better than that.

The algorithm

Let’s talk about binary search more in detail.

We will take the same array of prime numbers and will find 11 in the array again.

First, we decide which half of the array is 11 located in compared to the middle element (aka the median) of the set of numbers.

The middle element is 7 (index 3) and because 11 is greater than 7, we will drop the first half of the array and keep the second (right) one and redefine it as our new array: [11, 13, 17]. Note that 7 is not part of the new array as the number we want to find (11) is greater than the median, so there’s no point of keeping it.

We can now continue our search in the new array. The median of these elements is 13 (this is the middle element) and we compare 11 to this number. 11 is certainly less than 13, so we will keep the first (left) half of the array. Again, we can leave off the median and retain the numbers on its left. Not many numbers are left in this case, as our new array only contains one element ([11]), which is the number we are looking for.

Can you see what we have just done?

We kept dividing the array into two parts until we got only one element, the number we wanted to find. We didn’t inspect all numbers that are on the left of 11 as we did with the for loop but compared it to the current middle element. Instead of making five comparisons (for loop) we only made two until we found 11.

Of course, life is not always that simple but this quick overview of the algorithm shows that binary search needs less time and resource. I think you get the idea. The detailed analysis of binary search in terms of time complexity compared to the brute force method is beyond the scope of this post and will be covered in a later article.

The code

I will present two almost identical ways for doing binary search. The only difference is that the first one uses recursion and the second one involves everyone’s favourite, a while loop.

Recursive method

We will use the same numbers array, which contains the first seven prime numbers.

First we need to figure out how to halve the array. It’s a good idea to keep track of the lowest and the highest indexes of the array. If we continue to work with the left half, we redefine the highest index as the former middle element minus 1. (We won’t keep the middle element in the new array.) On the other hand, if we continue with the right half, we will make the lowest index to be equal to the former middle element plus 1.

So we need to define the low and high indexes first. Initially, low will be 0 (the first element of the initial array) and high will equal to the length of the array minus 1:

const numbers = [2, 3, 5, 7, 11, 13, 17];
let low = 0;
let high = numbers.length - 1;

The function is called binarySearch and this is how it can look like:

function binarySearch(element, low, high) {
  if (high < low) return 'The value cannot be found in the array';

  const mid = Math.floor((low + high) / 2);

  if (element === numbers[mid]) {
    return mid;
  } else if (element < numbers[mid]) {
    // in left half
    high = mid - 1;
    return binarySearch(element, low, high);
  } else {
    // in the right half
    low = mid + 1;
    return binarySearch(element, low, high);
  }
}

binarySearch accepts three arguments: element (the number we want to find the index of), low and high.

The first line (if statement) is necessary otherwise the function will run indefinitely (more on that later) and we don’t really want that.

We find out the index of the middle element first by adding low and high together and divide the result by 2. The parity of low and high might be different, so in order to avoid getting a fraction as a result of the division, we round the answer down to the nearest whole number.

Then we set up some conditional statements.

If the middle element of the array equals the number we want to find, we will be done and simply return the index of the middle element (mid). This will occur less and less often as we increase the length of the numbers.

If this condition is not met, we move on to the next condition, where we take the left half of the array. If the number we want to find the index of (element) is less than the middle element (arr[mid]), we will have to continue our search in the left half of arr. In this case we decrease the value of high to mid - 1. As it can be seen, we don’t physically divide the array into two parts but work on one half of it by manipulating the first and last elements. We move high closer to low to reduce the number of elements that can be considered. Now that we have a new value of high, we call and returnbinarySearch again.

In the third case, when the number we want to find is greater than the middle element, we will take the right part of the array by increasing the value of low to mid + 1 and return binarySearch with the new low value.

Whenever we call binarySearch again, we recalculate the value of mid based on the new value of low or high. Eventually, we will get to an array of one element and the value of mid is going to be the index of the element we want to find, so the algorithm finishes with the first if statement.

One more thing about the first line mentioned above. What if we want to find a number that is not included in numbers? For example, 8 is not a prime, so it would be very surprising if we found the index of it in numbers, which only contains primes. In these cases the repetitive invocations of binarySearch will result in low being greater than high after a while. This is not possible and we return a message that the number is not found in the array.

Binary search with while loop

This method is very similar to the previous one, the only difference that we won’t call the function recursively but will use a while statement to indicate when the function needs to stop searching (i.e. the element is not found in the array).

const numbers = [2, 3, 5, 7, 11, 13, 17];

let low = 0;
let high = numbers.length - 1;

function binarySearchWithWhile(element, low, high) {
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (element === numbers[mid]) {
      return mid;
    } else if (element < numbers[mid]) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return 'The value cannot be found in the array';
}

There’s not much to say here, everything works in a similar way as above.

Now let’s call the functions to find the index of 11:

console.log(binarySearch(11, low, high)); // 4

console.log(binarySearchWithWhile(11, low, high)); // 4

Both functions will return the same result.

Conclusion

Binary search might not seem to be easy at first but once one understands the principles behind it, it’s not that bad at all. It’s an effective way of finding elements in an array and the only condition is to have the array sorted.

Thanks for reading and see you next time.