DEV Community

loading...

JavaScript Binary Search Binary Search In JavaScript

johnkirtley_ profile image John Kirtley ・2 min read

Binary Search is an algorithm that allows you to quickly search through an array for a target item. Implementing it can also be a fairly common whiteboarding question when you're going through the interview process.

Why Would I Use This?

If you haven't worked with large arrays, you may wonder why you'd even want to learn this. Computers are so fast these days that searching through an array of 10, 20....100 items can take no time at all. However, what happens when your array consists of 2 million items? Searching for a particular target could take awhile.

This is where an algorithm like Binary Search comes in.

What Is Binary Search?

Binary Search allows you to quickly search through an array by cutting your search interval in half.

You will typically start in the middle of the array and check whether or not your target item is less than, greater than, or equal to the middle index. If it's smaller than the middle index, then you know that you'll only need to search the left half of the array. If it's greater than the middle index, then you know that you'll only need to search the right side of the array.

The algorithm keeps repeating this process until the middle index is equal to your target item. If your target item isn't present, then you could easily have the function return a -1 or false to indicate that what you're searching for isn't in the array.

Creating a Binary Search Algorithm In JavaScript

I've inserted a code snippet below that shows exactly how you can implement Binary Search using JavaScript.

Alt Text

Conclusion

Binary Search is a great algorithm to learn, especially when you're dealing with large amounts of data. It can quickly improve the time complexity of your applications from O(n) to O(Log n).

Thank you for taking the time to read this and I hope it was helpful.

Discussion (2)

pic
Editor guide
Collapse
bias profile image
Tobias Nickel

I still don't want to have an array of 2 million in Javascript. as even accessing a key on the array almost works like a search on its own in JS. Once I had an array of about 80 000, it was a wordlist, accessing a key more at the end, could take already several seconds.

Your algorithm will probably work good on a typed array such as Int32Array. Your example is good, but the strength of JS is in other places.

Thanks for the article.

Collapse
johnkirtley_ profile image
John Kirtley Author

Agree with you 100%!
I just stated 2 million to dramatize the potential use case lol.