Programming with JS: Binary Search

Understanding data structures, algorithms and basic programming concepts is essential for one to become a better developer. Nowadays most of those problems are solved using modern tools and libraries, but having deeper knowledge in that area will definitely broaden your perspective of software development.

Personally, for me it was pretty hard to get a grasp on some of those concepts, because I was not using them in my day-to-day work. I’m writing this series to improve my own understandings on those topics and help other people like me.

What is Binary Search?

Binary search is an algorithm used to find a particular item in a sorted list. It’s essential for the list to be sorted beforehand or the algorithm won’t be applicable. If you’ve ever dealt with binary search trees, this concept of this algorithm is similar.

We start by checking if the value we’re looking for is higher or lower than the middle item in the list. Why the middle? Here’s where the sorted part comes in. By checking whether the searched item is higher or lower than the middle you can then basically ignore one half of the array. If the item is higher it resides in the right part of the array (because it’s sorted beforehand). This means that you can leave the left part completely and search only in the one you’re interested in.

The above step is repeated throughout the array until you find your item. If at some point we reach a single item in the list and it’s value is different from what we’re looking for we know that our item is not in the list.

A situation in which this can be applied is looking for an item by an id for example. Maybe you’ve got a list of objects and every object contains an id. If the list is sorted you can use a binary search by comparing the items by their id property.

How does it work?

We start by selecting the bounds of the list — the start, the end and the middle. The middle is calculated by adding the start and the end and dividing them by two rounded down.

Then we check if the middle item is what we’re looking for. If it’s not we check if it’s higher or lower. Depending on that we change the boundaries. If our item is lower, we set the end to be equal to the middle minus 1. If it’s higher then we set the start to be equal to the middle plus one. The middle is ignored because we already know that it’s not what we’re looking for. Then we recalculate the middle — start + end divided by 2 and rounded down and go again. We repeat this until we find our item or we reach a single item which is different than ours.

If you haven’t worked with binary search trees or heard of that algorithm before it sounds a little bit overwhelming at first. But the fact that you don’t need to go through every item in the list is a big plus. The only thing is that you need the list of items to be sorted beforehand, otherwise binary search will not work.

Here’s the actual code for the algorithm:

Thank you for the read, if you’re looking for more computer science JS stuff, I’m currently writing a whole series on them. If you want general JS content, you can take a look at my profile.

Programming with JS:

Recursion: https://hackernoon.com/programming-with-js-recursion-31371e2bf808Merge Sort: https://medium.com/@KondovAlexander/programming-with-js-merge-sort-deb677b777c0Binary Search: https://medium.com/@KondovAlexander/programming-with-js-binary-search-aaf86cef9cb3Insertion Sort: https://medium.com/@KondovAlexander/programming-with-js-insertion-sort-1316df8354f5