Understand and Implement Binary Search In JavaScript.

Photo by Joshua Aragon on Unsplash

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

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

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

  • 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

Binary Search implementation
Binary Search implementation

Practice

Conclusion

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.

Developer, Book lover.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store