Binary Search Made Easy

Have you ever picked up a dictionary to search for a particular word? Guess what, you are likely performing a Binary Search. How? I hear you ask through the Grapevine. Imagine you’ve been asked to search for the word terrarium in a dictionary.

One way to approach the task is to search the dictionary from front to back A through Z in a linear fashion but it’s a waste of good time. Certainly not a very developer-esque approach.
A natural approach is to split the dictionary two ways. For example, A-M, N-Z, using the first letter t in terrarium as a hint telling us which half of the book to start our search. In this case, t is in the section of N-Z, so that’s where we start. We simply repeat the process all over again until we find it. Voila!

Why Binary Search?

Binary Search is a quick algorithm particularly when compared with a linear search. Only half the data is searched at any step. For example, it is possible to search through 1024 values in 10 steps, every time.

Note that Binary Search is only useful out when you have a sorted list of items, i.e A-Z.

To implement Binary Search elegantly we need to write the function recursively. A Recursive function is simply a function that calls itself with different parameters.
A non-recursive solution also exists, see here.

To the Code 👉

To bring this idea to life, let’s try locating the number 17 in an array [1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35]

First lets define the Function scaffold so we know where things go

function binarySearch(SampleArr, item) {
    // code goes here
};

let SampleArr = [1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35];
let item = 17;
let itemIndex = binarySearch(SampleArr, item);

Define the middle position and item

function binarySearch(SampleArr, item){
    const midPoint = Math.floor(SampleArr.length / 2); 
    const middleElem = SampleArr[midPoint];
};

Set Condition for when middle item is what item we’re searching for

function binarySearch(SampleArr, item){
    ...
    // if middle item is right, lucky us no further search required
    if (middleElem== item) {
        return item;
    }
};

When middle item < item, we carry on searching recursively in the left subset of data I.e array from position 0 to midPosition

function binarySearch(SampleArr, item) {
    ...
    else if (item < SampleArr[midPoint]) {
        // search item from left subset
        return binarySearch(SampleArr.slice(0, midPoint), item);
    }
};

When middle item > item, we carry on searching recursively in the right subset of data I.e array from position midPosition to the end of the array

function binarySearch(SampleArr, item){
    ...
    else if (item < SampleArr[midPoint]) {
        // search item from right subset
        return binarySearch(SampleArr.slice(midPoint+1), item);
    }
};

Lastly we want to return null when we can’t locate the item in the array

function binarySearch(SampleArr, item){
    ...
    else {
        // when we can't binarySearch an item 
        return null;
    }
};

Finally…

function binarySearch(SampleArr, item) {
    const midPoint = Math.floor(SampleArr.length / 2); 
    const middleElem = SampleArr[midPoint];        
    // if the middle item is right, lucky us no further search required
    if (middleElem == item) {
        return item;
    } else if (item  SampleArr[midPoint]) {
        return binarySearch(SampleArr.slice(midPoint+1), item);
    } else {
        return null;
    }
};
        
let SampleArr = [1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35];
let item = 17;
let itemIndex = binarySearch(SampleArr, item);

Hope this has helped you level up your knowledge on binary search. Go on, give it a go.

Ta