# Binary Search - JavaScript

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!