Ep.5 Data Structures and Algorithms with JS - Binary Search

Cover Image for Ep.5 Data Structures and Algorithms with JS - Binary Search

Be advised! This post is part of the series: Data Structures and Algorithms with JS therefore before continue to read I suggest you the introduction to this series of posts if you haven't read yet. Thanks.

Imagine you have a yellow pages book that has 10000 pages and you need to find Michael's phone number in there.
You wouldn't go page by page and name by name to find Michael's phone number (this is called linear search in CS), instead you would jump to the middle of the book and start from there.

Binary Search works basically the same way, starting at the middle then from there check if the current item is the the same as the one need to find.

Let's say you want to know if number 8 is in a list of 10 elements. Binary Search will start at 5 and then check if the current position (middle) is what looking for then return correct (the position of the element or the element itself), low (when the current position is less than what looking for) or high (when the current position is greater than what looking for) and continuing iterate from there eliminating half and checking correct, low, high.
Making Binary Search Log2(n). That's why Binary Search is very efficient even for massive collections.

Another take away is that Binary Search requires sorted (ordered) list.

const binarySearch = (list, item) => {
    let low = 0;
    let high = list.length - 1;

    while (low <= high) {
        let mid = Math.floor((low + high) / (2)); // Math.floor makes number integer
        let guess = list[mid];

        if (guess === item) {
            return guess;
        }

        if (guess > item) {
            high = mid - 1;
        }

        if (guess < item) {
            low = mid + 1;
        }
    }

    return null;
}

binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 8);

Thanks.


More Stories

Cover Image for Using ChatGPT as your nutritionist

Using ChatGPT as your nutritionist

While ChatGPT is primarily known for its conversational abilities, it can also serve as a virtual trainer and nutritionist, providing personalized guidance to help you achieve your health and wellness goals.

Cover Image for How to invest in the stock market - a beginners guide

How to invest in the stock market - a beginners guide

There is so much bad information on how to invest in stock market causing a lot of confusion for people that want to get started in investing that I decided to create a guideline for beginners based on Peter Lynch work