JavaScript & Binary Search

Since I started learning about algorithms, most examples and explanations I come across are usually in languages unfamiliar to me (yet), like Python, Java, etc. That’s why in this article, I want to unpack what I've learned using Binary Search and JavaScript. I also wanted to shout out BrightCode’s Algo course, which has been really helpful.

1. I want to explain binary search by using an everyday example (practical/relateable )

2. I’d like to walk through a more technical example of a binary search code in JavaScript.

Binary Search in an Everyday Example

One of my favorite metaphors for binary search is a guessing game. Let’s say you and your friend (Karen) are playing a guessing game to see if you can guess the number Karen is thinking. The number is between 1 -100. If you guess wrong, she’ll tell you either too high or too low.

FYI Karen is thinking of the number 18, but let's pretend we didn’t know.

There are usually about 4 popular strategies.

1. Start guessing random numbers, hoping you get it in a few tries.
2. You guess each number in the order or reverse order.
3. Since you and Karen go way back, you guess her favorite number or birth month.
4. You try to eliminate as many possible options to make a more accurate guess. So you start by guessing the number 50. Whether Karen says it's too high or too low, it literally cuts your options down by 50%. This is where we start thinking like a binary search algorithm.

Karen responds, “50 is too high.” So then you guess 25 because you want to cut the options down by 50% again. Karen says, “too high.”

Again you want to eliminate the most options possible, so you choose half of 25, 12.5. The convention in binary search is to round down(although you can round up too), so you say 12. Karen says, “ Too low,” for the first time! So that means we are getting closer.

Since there are 12 options left, 12/2 would be 6. Since the last guess was 12 and it was too low, If you move up 6 boxes up from 12. We then land on 18, and Karen says, “that we guessed right! ” We got the answer in 5 guesses, which is pretty fast.

Imagine how many more guesses it would have taken if we guessed each number beginning at 1, and Karen was thinking of the number 100 instead. It would have taken forever. That would have been an example of a simple search algorithm that is much slower than a binary search.

What Exactly is Binary Search?

Binary search is an algorithm strategy to obtain the target number within an ordered array. Binary search will not work with an unordered array! Thinking through binary search, we want to eliminate as many options as possible by cutting the list by half until it gets through the entire list and checking if we hit the target number or not. It’s a fast algorithm with a worst-case O(log n) performance and a beneficial tool for tackling complex future algorithms.

JavaScript Example of Binary Search

The example above returns the target number being karensNum if present, else it returns -1.

The difference between the guessing game example and the code example is that in the guessing game, you don’t know what number Karen is thinking of, and in the code, you do. Often when completing LeetCode, HackerRank problems, you don't know what the ordered list you are getting or the target value in the test cases, but you need to create the logic to find if it exists the given ordered array. I hope the examples above help unpack an introduction to binary search with JavaScript.

Thank you for reading the article! I hope you found it helpful.