Solving The Binary Search Algorithm With JavaScript

This is a popular searching algorithm and today we’ll discuss how to go about solving this with JavaScript. Let’s start with the prompt:

“Write a function that takes in a sorted array of integers as well as a target integer. The function should use the Binary Search algorithm to determine if the target integer is contained in the array and should return its index if it is, otherwise return -1.”

Now we have the prompt, but let’s take a quick step back so we can think of what Binary Search actually is. In all honesty, the odds are high that you may have used this algorithm sometime during your life. For example, let’s say that you need to look up a word in a dictionary, and suppose that word is “bumfuzzle” (it means to confuse). One way to approach this would be to look at each word from that first page until you find word you’re looking for, but this isn’t an efficient way to search. The optimal strategy would be the following:

1. Open the dictionary to it’s halfway point (approximately)
2. What letters are the words beginning with? Suppose the halfway point consists of words that begin with “L”
3. Since we know a dictionary is sorted alphabetically, and the word we’re looking for is “bumfuzzle,” we can come to the conclusion that our word, that starts with the letter “B,” must be in the first half of the dictionary. So there’s no need to look at the second half. Essentially, removing the amount of items we need to search by half.
4. Now, go to the halfway point of the first half of the dictionary. (If the word would be in the second half, then we would go to the halfway point of the second half of the dictionary)
5. Repeat steps 1- 4 until the word is found.

The above steps of finding a word in a dictionary is a great example of how the Binary Search algorithm works.

Now that we have a basic idea of how the algorithm works, let’s plan how we can write the necessary code.

The Plan

1. We can create two pointers, left and right. These will represent the to the two ends of the input array. So, the left counter will be the first element in the array, and the right counter will be the last element in the array, and we’ll take note of the indices of these pointers.

2. We can create another variable that will represent the middle of the array by taking average of the left and right pointers.

3. Create a third variable that we can use to compare the element in the array to the target integer. We can name this “potentialMatch”

4. At this point we can use an IF statement for our comparisons.

First, we’ll compare the target integer to our potentialMatch, if it’s a match we can return the index of the the potentialMatch.

If it’s not a match and if the target integer is less than the potentialMatch, we will have to go through another loop of the algorithm, so that we can traverse through the first half of the array.

Else, if the target integer is greater than the potentialMatch, we can go through another loop of the algorithm, so that we can traverse through the second half of the array.

The Execution

We can initialize the Binary Search function like so:

Since we planned to use arguments that can’t be included with the function above, we can create a helper function and use the necessary parameters with it. Then, simply call the helper function within the binarySearch function.

The first step was to create the left and right pointers, which are being used as arguments for the helper function. Now we need to compare them to check if the left is greater than the right pointer. At this point, if the left is greater than the right pointer, then we cannot perform the Binary Search algorithm, since Binary Search can only be applied to a sorted list. If the first element is greater than the last element, the list isn’t sorted.

The question prompt didn’t mention what to return if this is the case, so during an interview you may need to ask the interviewer. I’ll assume we need to return a -1.

Now we need to create two variables, to represent the middle of the array and the potentialMatch.

With all the variables and initial logic created, we can work on the final logic that will compare the target integer to the potentialMatch.

If the target and potentialMatch are equal, return the middle variable, because it is the index of the potentialMatch.

If the target is less than the potentialMatch, go through the helper function again with the “right” argument set to <middle -1>, this way the second half of the array will be removed from the search.

If the target is greater than the potentialMatch, go through the helper function again, this time with the “left” argument set to <middle + 1>, this way the first half of the array will be removed from the search.

With that, the helper function is complete and we can invoke it within the original binarySearch function. When calling the helper function, the left argument should be set at 0, since the left-most element will always be at index 0. The right argument should be set as the index of the final element of the array, which can be set as <array.length - 1>.

As a result, the final code should look like:

And there you have it. A solution to the Binary Search algorithm.

A quick complexity analysis will show that the time complexity of this solution is O(log(n)), where (n) is the length of the input array. But why “log?” The reason this solution is O(log(n)) is because through every traversal of the array, we cut our search terms by half.

As for the space complexity of this solution, it will be the same as the time complexity. The space complexity is O(log(n)), and this is because of the memory usage for every traversal of the input array.

Thank you for reading this article on Binary Search and I hope you find it useful. Although this is a solution, I found a better way to implement it that will result in a space complexity of O(1). I’ll get into that solution in another article.