Binary Search - JavaScript

4 min readFeb 25, 2021

As a programmer, you’ll consistently encounter a problem such as this…

“Hey, remember that array that you’ve been storing tons of important values in? Great! Well… now I need you to find X, and make sure you find it as fast as possible!”

This is the exact reason why learning search algorithms as a programmer is important! You’ll never know when you need to search through your array so if you ever encounter a problem such as this, you’ll know what to do.

Let’s tackle a simple search algorithm together:

“I want you to find the number 99 in this array of random numbers I have in order. I’m even not sure if 99 is in there, but if it is let me know!”

Heres the array we’re searching through:

[1, 3, 5, 12, 16, 24, 25, 27, 33, 37, 42, 45, 50, 53, 56, 64, 65, 77, 80, 83, 86, 89, 99, 112]

…so, lets think about this problem. An obvious strategy is to just iterate through the array, starting off at the first index, going up one by one until we encounter our number 99. This would be what is known as a linear search. Lets implement this strategy:

I created a function called linearSearch that takes an array and a targetValue.
I initialized a for loop, that loops until i is no longer less that the length of the array passed in.
On every loop, I check if the array at index i (array[i]) is equal to the targetValue passed in.
If the numbers are equal, the congrats we found it!
If the numbers aren’t equal, then the loop repeats
If the entire array is searched, then we return false and say that we can’t find the targetValue (It’s not in the array)

As you can see in my tests below the function, I search for the number 99, which is indeed inside of the array so the value 99 is returned to me!

As for my second test, I search for the number 22, which is not inside of the array so I am told that the function cannot find my number.

While this is a working strategy, it’s not the most efficient, and here’s why.

As you can tell by looking at our array, 99 is at the end of the array, meaning we had to look through almost every index of the array before we found our targetValue! There’s got to be a better way!

In comes Binary Search

Binary Search

Binary search is an algorithm in which we search through a sorted list of items. The strategy behind this algorithm is to divide the list in half on every guess to narrow down the possible options of our targetValue

Let’s use our problem example above for this implementation of the search. we still have our same array of numbers:

[1, 3, 5, 12, 16, 24, 25, 27, 33, 37, 42, 45, 50, 53, 56, 64, 65, 77, 80, 83, 86, 89, 99, 112]

Lets write a way to solve this problem.

We’ll want to have a minimum value and a maximum value. the min will be set to zero, and our max will be the length of the array-1
We’ll need to split the array in half, like a true binary search function! We can use our min and max values to help! To find the center of the array, we’ll want to find the average of the arrays length: (min + max)/2. Our average may not always be an integer, so we’ll want to round down. This number will be our guess!
Using our guess, we’ll first want to see if we guessed correctly! (array[guess] === targetValue)
If the guess is less than the targetValue (array[guess] < targetValue), we’ll want to increase our guess. Remember, guess is the average of min and max, so how do we increase the average? By increasing min! We’ll want to set min equal to our guess + 1.
If the guess is more than the targetValue, aka the opposite of what #4 explained, then we’ll want to decrease the max value: max = guess-1
Repeat from step #2

If you run this, including the test problem at the bottom, You should get 99 in 5 guesses, meaning we only check 4 numbers before we got to our targetValue! Thats much more efficient than checking all of the other numbers in the array. If we had an array that had a length of 100, our computer would certainly thank us for using the binary search algorithm!

I hope you now see the usefulness in understanding a binary search algorithm, and I hope this article has proven useful to you. Happy coding!