Binary Search — What is it and How Do I Do it?

As a new bootcamp grad, I have much to learn. Lately, I have been focusing my time on algorithms so I can ace future technical interviews. However, I tend to speed through lessons and then when approaching a practice problem, I say to myself, “ I learned this, but I forget how to implement it.” Not a great way to start! In order to solidify these concepts, I thought I could dedicate some of my blogging to developing my approach. One of the first algos I thought of was binary search — I’ve seen fellow cohort grads use it, I’ve watched lessons about it, but I have yet to successfully use it myself. So I’m going to go over some basics — here we go!

What is Binary Search and Why is it Useful?

Binary Search is an algorithm! Binary Search is useful when we are looking for an element within a big list of sorted elements. It’s useful because it’s much faster than, say, a simple search. To explain the difference, I like the analogy of two friends playing a guessing game with one another — Annie asks Jenna to guess what number she is thinking of between 0 and 100. For every answer, Annie will say if her guess is too low or too high. Jenna starts by saying “1”
Annie: “Too low”
Jenna: “2”
Annie: “Too low”
Jenna: “3?”
Annie: “Nooo..too low”
…You can see how tiresome and inefficient this could be if Annie’s number was 99. Each time Jenna guesses, she is eliminating only one possibility. This is an example of simple search! For the most part, not that great of a method.
Now, lets say Jenna learns a thing or two and they play again, but this time Jenna starts with “50”
Annie: “Too low”
***NOW JENNA HAS ELIMINATED 50 NUMBERS, WOW***
Jenna: “75”
Annie: “Too Low”
Jenna: “87”
Annie: “Too High”
***JENNA HAS NARROWED IT DOWN TO 12 NUMBERS!!***
Jenna: “81”
Annie: “omg yes! You’re so smart!”

See how fast that was? Jenna used binary search to guess the correct number. She guessed the middle number to eliminate large chunks of numbers at once — some developers refer to this method as divide and conquer. We can see how much faster (and less annoying) this approach is than simple search.

Cool! Now how do we implement that in our code?

Visualization for Binary Search

So let’s break this down step by step. Here is our array of numbers:

numArray = [1,2,4,6,8,10,16,20]

We wanna know if ‘16’ is in this array. So we need to find a middle point (like Jenna’s 50). To do this, we need to define our starting point and end point.
Our starting point is the beginning of the array and our end point is the length of the array minus 1 (to get the correct index):

let startIndex = 0
let endIndex = numArray.length - 1

Perfect! Now getting our middle point is a bit easier — we just add up our starting and ending index and divide by two. In our case that would be ‘3.5’ which isn’t an index we can point to. Here we wanna use Math.floor() to round down to a whole number:

let middle = Math.floor((startIndex + endIndex) / 2)

So now, the idea is that we compare our middle number (at the index of ‘3’) with our target number, ‘16.’ In this example, our middle number is ‘6’ which is less than our target, so we can eliminate everything from our middle to our start. We then need to reassign our startIndex to the number right after our middle point and search again. This will require a loop — we want to keep looping while our startIndex is less than or equal to our endIndex to ensure we traverse the whole array:

while (startIndex <= endIndex) {
   let middle = Math.floor((startIndex + endIndex )/ 2)
   if(numArray[middle] < target) {
     console.log("your target is larger, searching again")
     startIndex = middle + 1
   }
}

But what if our target was less than “6”? We need another if statement that would then move our endIndex over to the position right before our middle point. Here is our added code :

while (startIndex <= endIndex) {
   let middle = Math.floor((startIndex + endIndex )/ 2)
   if(numArray[middle] < target) {
     console.log("your target is larger, searching again")
     startIndex = middle + 1
   }
   if (numArray[middle] > target) {
     console.log("your target is smaller, searching again")
     endIndex = middle - 1
   }
}

We now have the bulk of our code. We just need to check whether our middle is the same as our target or if our target cannot be found. Below is our binary search function in its entirety:

function binarySearch(numArray, target) {
   let startIndex = 0
   let endIndex = numArray.length -1
   while (startIndex <= endIndex) {
      let middle = Math.floor((startIndex + endIndex )/ 2)
      if(numArray[middle] < target) {
         console.log("your target is larger, searching again")
         startIndex = middle + 1
      }
      if (numArray[middle] > target) {
         console.log("your target is smaller, searching again")
         endIndex = middle - 1
      }
      if (numArray[middle] === target) {
         return console.log("Congrats! Target found!")
      }
      else {
         console.log("Target was not found")
      }
   }
}

Tah-Dah! We did it!
Binary search is a great algo option to use over simple search. The only caveat when considering implementing binary search is that the array has to be sorted.

Give it a try yourself. Next time, I would like to develop on our binary search skills and learn how to use recursion (OoOoOoooh)!

Have fun!