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

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.

--

--

--

MERN Stack Developer | Book lover | Also a Procrastinator

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Mr Frontend weekly link sharing #45

Important Notes on JavaScript

React NextJS Instagram feeds UI with TailWind CSS Part 3— Create Post and Posts component, add the…

End node process

The difference between Arrow Function and Regular Functions

Free Hosting of Web Applications using Angular and GitHub Pages

Adding Microsoft Jheng Hei 正黑體 Font to PDF with Node.js pdf-lib

Custom select/dropdown in React

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
Akibur Rahman (Akib)

Akibur Rahman (Akib)

MERN Stack Developer | Book lover | Also a Procrastinator

More from Medium

Javascript: Function Expression vs Function Declaration

Confused between AngularJS and ReactJS? Let’s make it simpler for you!

AngularJS and ReactJS

Unite Unique Values With JavaScript

Javascript, write it clean PART 1 : variables.