Binary Search in JavaScript

Published May 1 2022

What is binary search?

Binary search is a 'divide and conquer' algorithm that finds the position of a specified input value within a sorted array. With a Big-O

runtime of O(log n)

, it is an efficient way to search large sorted arrays. The name 'binary' is derived from the fact that it divides the array upon which it is operating into two halves. In this post, we will see binary search works and how it can be implemented in JavaScript.

Simple search

Suppose we want to find an element with a specific value in a sorted array - like a person in a phone book

.

One of the simpler ways to do this would be to start at the first element, check if it is equal to the value we are looking for, and if not, move on to the next element. We could continue this until we find the value we are looking for. This is known as simple search and can be seen implemented in JavaScript in the playground below.

The issue with simple search is that with each guess, we are only eliminating one element in the array. So in the worst case, where the search term happens to be the last element, we will have to check every element in the array. Put differently, simple search has a time complexity of O(n)

. We can do much better than this with binary search.

How does binary search work?

Suppose that instead of beginning our search at the start of the array, we begin at the middle of the array and compare the element there to our search term:

Since the array is sorted, we will know that if the search term is less than the element in the middle of the array, we can eliminate the upper half of the array. Similarly, if the search term is greater than the element at the middle of the array, we can eliminate the lower half of the array. So in the case where we are searching for "Zack", we will see that its value is greater than the middle term "Arnold" and so we can deduce that "Zach" is in the upper half of the array.

So in one operation we can remove half of the input array from our search. Much more efficient than simple search! We can then use the same process on the upper half of the array to again remove half of it from our search.

This process continues until we have either found our search term or narrowed down the array to a single element.

Binary search example in JavaScript

Let's look at how this can be implemented in JavaScript:

In the implementation above, the binary search function is called recursively

until either the search term is equal to the middle element or the length of the sub-array being searched is 0. Try logging start and end inside the binarySearch() function to see how they change in different invocations as we hone in on the search term.

Binary Search Time Complexity

We have seen in practice why binary search is so efficient compared to simple search. In one step, it is able to elimate half of the dataset, while simple search can only elimate one element. This efficiency results in a time complexity of O(log n)

. This means that, as the dataset grows, the time it takes to find an element using binary search grows at a much slower rate. However, is important to note that binary search requires that the array be sorted before searching, which can add extra time and complexity to your code.