Divide and Conquer: Binary Search in JavaScript

In the beginning, you will most likely try to use a brute force method to solve search problems; this is because it is the easiest and most rudimentary way to find a target. However brute force has a time cost; The Big O notation of brute force is usually and unacceptably equal to or greater than bigO(n²).

If you can make something work with the brute force technique you will most likely need to refactor it later. We have talked about bubble sort in JavaScript in the past. I mentioned that bubble sort uses the brute force technique for sorting an array in that article. Sorting has a time cost but it is needed to use Binary Search which has a bigO(log n).

Generally, when implementing a search problem you are better off to search from a sorted list. You can think about looking at a random list of Apartments from a google search. Now think about looking at a google list of Apartments sorted by distance from you. Generally sorted lists are much more useful. Binary Search will not work for an unsorted list because it uses a sort of educated guess; you cannot make educated guesses on random and arbitrary lists.

The first step in Binary Search is to sort the list so we can make an educated guess about where the target is located. You can use the built-in JavaScript methods.

However, I will reinvent the wheel because we are learning algorithms in JavaScript. You won’t be a JavaScript master until you can master the fundamentals first. These are the atoms of our universe and it’s good to know how to they interact with other the atoms of JavaScript. 

let newArr = []
function insertionSort(arr) {
   
    if (arr.length > 0) {

        function findMinAndRemove(arr) {
            //insertionSort helper method to remove min value from array an recurse
            let min = arr[0];
            //sets min value to first element
            for (let i = 0; i < arr.length; i++) {
                if (min > arr[i]) { min = arr[i] }
                // if  the i'th element is smaller reassign min value to it
            }
            newArr.push(min);
            // add smallest element to new array and recurse
            arr.splice(arr.indexOf(min), 1)
            return insertionSort(arr)
        }
    } else {
        
        return newArr
    }

    return findMinAndRemove(arr)

} 

Now that we have our sorted array we can make intelligent guesses on it. The standard implementation of binary search is: 

1. Start a while loop that will terminate if the target is not found: Here I use (end > start.)
2. Look at the middle of the array, that can either be what you were looking for or it can be too high or too low. 
3. If it was too low you just ruled out the top half of the array. Conversely, if it was too high you just ruled out the bottom half of the array. Reassign the start index or the end index to the guess index. Now you are only looking at the bottom half or top half or the array.
4. You reassign your guess to the middle of the halved array. 

Lets Code it out: 

function binarySearch(arr, target){ 
    //start will be the first index 
    let start = 0
    //end will be last index 
    let end = arr.length-1   
    
    //guess is typically middle of array 
    let guessIndex = Math.floor((end - start) / 2) 
    
    while(end > start){ 
        console.log(start, end)
    if (arr[guessIndex] === target){
        console.log("found at index") 
        return(guessIndex)
    } else if (arr[guessIndex] > target){ 
        //this means our guess was too big. It also means we don't need the end-half of the array. 
        //we reassign end to our guess. Now our array is halved. We also  reassign guess to the middle of the bottom half of 
        //our array. Now end just got closer to start and we have narrowed our search 
        console.log("guess too big && guessIndex", guessIndex)
        end = guessIndex; 
        guessIndex = Math.floor((end + start)/2) -1
        
    } else if (arr[guessIndex] < target){
        //this means our guess was too small we will reset our start to the guess index and look again.
        console.log("guess too small && guessIndex", guessIndex)
        start = guessIndex; 
        guessIndex = Math.ceil((end + start)/2) 
       
    } else { return "NOT FOUND"}
    }
} 

Looks good. Lets break it down line by line:

while(end>start){...code will run

Here we are starting a condition that ensures the code will run until it returns false. Now we can reassign values that will trigger arr[guessIndex] === value to return true.

if (arr[guessIndex] === target)

This is the condition we want. Once this is true our search is over, the next block of code is if our guess was too high:

else if (arr[guessIndex] > target){ 
        //this means our guess was too big. It also means we don't need the end-half of the array. 
        //we reassign end to our guess. Now our array is halved. We also  reassign guess to the middle of the bottom half of 
        //our array. Now end just got closer to start and we have narrowed our search 
        end = guessIndex; 
        guessIndex = Math.floor((end + start)/2) -1
        
    }

This tells us our guess was too large. arr[guessIndex] will evaluate to whatever is at the index. So if guessIndex was 0 this would be the value at arr[0]. Since our array is sorted we know that our target is smaller. We now take that information and reassign our end to the guessIndex.

This means we are only looking at values in the first half of the array. We also have to reassign our guessIndex to:

guessIndex = Math.floor((end + start)/2) -1

Lets say our target was 2 in the array [2,4,5,30,99]. Our starting guessIndex is

let guessIndex = Math.floor((end - start) / 2) //=> 2

This gives us the original guess value of:

arr[guessIndex] //=> 5

Let's break this down. We take the end and start and add them together. Then we divide 2. Then we subtract 1.

2+0 //=> 2 
2/2 //=> 1 
Math.floor(1) //=> 1 
1 - 1 //=> 0

guessIndex will thus evaluates to 0 now and if our value and target was 2 at index 0 this will trigger arr[guessIndex] === value to be true ending the while loop and returning the value.

Lets look at the next block of code if the guessIndex was too small:

else if (arr[guessIndex] < target){
        //this means our guess was too small we will reset our start to the guess index and look again.
        start = guessIndex; 
        guessIndex = Math.ceil((end + start)/2) 
       
    }

This shifts our focus to the top half of the array. Our halved array will now start at the guess as we know the target is not lower. Now our guessIndex becomes:

guessIndex = Math.ceil((end + start)/2)

for the array [2,4,5,30,99] our guess will initially be 2;

Lets look at what our code will do: If our start is reassigned to 2.

end + start //=> 5 + 2
7/2 //=> 3.5 
Math.ceil(3.5) //=> 4

arr[guessIndex] will return the element at the 4th index.

Lets programmatically test this. I tested an array for all the values of the array and then some not in the array.

for (let i = 0; i < sortedArray.length; i++){
console.log(binarySearch(sortedArray,sortedArray[i]), "found", sortedArray[i]) 
}  

console.log("TEST", binarySearch(sortedArray, -1)) //=> undefined

console.log("TEST2", binarySearch(sortedArray, 100)) //=>undefined 

To recap, the idea of Binary Search is to divide the array in half each time you guess incorrectly. Honing in on a target with a too large or too small control flow. Each incorrect attempt resetting your guess index to the middle of the newly halved array.

Lead image by Ferenc Almasi on Unsplash.