Understand and Implement Binary Search In JavaScript.

3 min readJun 28, 2020

Let's play a game!

You have to guess a number. The number should be between a range (Like 1 to 100). Just you have told me the range of that number. I will find which number you guess by asking some questions. But I can not ask this one "What is your number?".

Say, you guess 56 from the range of 1 to 100.

What do you think about how will I find you guess 56 by asking questions?

First approach

I can ask you like —

Is your guessed number 1?

You: No.

Is your guessed number 2?

You: no.

….

Is your number 56?

You: yes.

Finally, I find your number! But if you guess 100, I have to ask the same question 100 times. This approach called Linear Search. Linear Search's time complexity is O(n).

Second approach

I can ask you like —

Is your number equal or less than X? (where X = middle of the range)

So let's start, Is your number equal or less than 50?

You: Greater.

You say, Greater. That means Your number must be the right side of the range(51 to 100). Now I can omit the left side of the range (1 to 50).

Is your number equal or less than 75?

You: Less.

You say, Less. That means Your number must be the left side of the range(51 to 74). Now I can omit the right side of the range (75 to 100).

Is your number equal or less than 62? (Middle of the range is 62.5. Here we omit the floating part.)

You: Less.

You say, Less. That means Your number must be the right side of the range(51 to 61). Now I can omit the left side of the range (62 to 74).

Is your number equal or less than 56?

You: Equal.

Woohoo! finally, I get you. This approach called Binary Search. Binary Search’s time complexity is O(log n).

Before looking at my pseudo-code or implementation, I encourage you to give a shot on your own.

Pseudo Code

Declare a function with two params (sorted array, targeted value)
Create a left pointer at the start of the array and a right pointer at the end of the array.
While the left pointer is less than or equal to the right pointer:

— Create a pointer in the middle.

— If the middle pointer's value is equal to the targeted value, return the index.

— If the middle pointer’s value is greater than the targeted value, move the right pointer down (middle pointer minus 1).

— If the middle pointer’s value is less than the targeted value, move the left pointer up (middle pointer plus 1).

— Repeat previous steps until you found the targeted value.

While the left pointer is greater than the right pointer return -1.

Implementation

Practice

Now you know what Binary Search actually is. It's time to practice and apply what you learn. To get Binary Search related problems from Leetcode click here.

Conclusion

Did you notice one thing? Binary search does not work without a sorted array. The reason is, you can not compare the targeted number with the middle of the range if the array is unsorted.

Now you can say that Linear Search is better than Binary Search.

It depends, If you are searching for once there is Linear Search is better. But you search more than once there is Binary Search much better. Use them as your requirement is.