Learn Binary search algorithm with JavaScript and how to make it better.

Welcome to this tutorial, in this lesson, you will learn how to use the binary search algorithm using JavaScript and how to make it better.

Hey, wait! If you want it as a video, watch it below:

The binary search algorithm can be very useful whenever we want to search for the presence of an element in an array of elements. Using linear search is slower, especially when there is a need to search a large dataset. For example, searching for 1,000,000 in an array that contains five million numbers.

Whoots! It will take 1 million iterations to do that provided we use linear search but binary search makes it a lot faster.

Do you really want to understand the binary search algorithm using JavaScript? Then, I will ensure you understand it by the time you get to the end of this article. Now, what is binary search?

What is Binary Search?

Binary search is an algorithm that finds the index of a target value from a sorted array of numbers by dividing the array into two parts and comparing the target value with the element at the midpoint until the target value is found. The binary search algorithm operates by neglecting half of the list on every iteration because it is sure the search term can't be found in them.

Sometimes you want to search for a certain number from a sorted array of numbers but without a common difference, especially when you’re dealing with a large dataset, then you can use binary search algorithm. Let's use the array and searchTerm below as an example:

const searchTerm = 10;
const  numbers = [1,  3,  4,  6, 7, 8, 10, 14, 18, 50];

How can you know the index of 10 to pick it from the array? Well, you can’t except do linear or binary searches. Using linear search, in this case, maybe slow and boom, the binary search comes to the rescue.

Binary search algorithm step by step using JavaScript

Step 1: Get the first and last index of the array

const searchTerm = 10;
const  numbers = [1,  3,  4,  6, 7, 8, 10, 14, 18, 50];

let firstIndex = 0
let lastIndex = numbers.length - 1;

Step 2: Calculate the midpoint and determine the result repetitively

for(let index = 0; index < numbers.length; index++ ) {

    const midpoint = (lastIndex + firstIndex) / 2;
    const itemAtMidpoint = numbers[midpoint];

    if ( searchTerm === itemAtMidpoint ) {
        console.log( "found", itemAtMidpoint )
        return "Item is found";
    }

    if ( itemAtMidpoint > searchTerm ) {
        lastIndex = midpoint - 1;
    }

    if ( itemAtMidpoint < searchTerm ) {
         firstIndex = midpoint + 1;
    }
}

Now let's explain how step 2 works step by step:

sub-step 1: find the item at the midpoint.

const midpoint = (lastIndex + firstIndex) / 2;
const itemAtMidpoint = numbers[ midpoint ];

sub-step 2: check if the searchTerm is equal to the item at the midpoint

if (searchTerm === itemAtMidpoint) {
    console.log( "found", itemAtMidpoint )
    return "Item is found";
}

If the item at the midpoint is equal to the searchTerm, then we have found the number we are looking for and then we returned it.

sub-step 3: Reset lastIndex for the next iteration based on a condition.

if ( itemAtMidpoint > searchTerm ) {
    lastIndex = midpoint - 1;
}

If the item at the midpoint is greater than what we're searching for, then we need to search for it among the numbers that are less than the item at the midpoint: [1,3,4,5]

To do that, we have to calculate another midpoint, since we're sure the item at the midpoint is greater than what we're searching for then we have to cut out the item at the midpoint and any numbers greater than it.

So we reset the lastIndex to be used in the next iteration to midpoint - 1, which means the next lesser item to the item at the midpoint. Then the array the next iteration will use starts from index 0 and ends at index midpoint - 1;

For example,

const searchTerm = 4;
const numbers = [ 1, 2, 4, 5, 7, 8, 9, 10, 12]

if the item at the midpoint (7) is greater than what we are searching for, then the index of the array for the next iteration will start from 0 and ends at ( midpoint - 1). This process will be repeated until the item is found.

sub-step 4: Reset the first index for the next iteration based on a condition.

if ( itemAtMidpoint < searchTerm ) {
    firstIndex = midpoint + 1;
}

If the item at the midpoint is less than what we're searching for, then we need to search for it among the items that are greater than the item at the midpoint.

To do that, we have to calculate another midpoint, since we're sure the item at the midpoint is less than what we're searching for then we have to cut out the item at the midpoint and any numbers less than it.

So we reset the first index of the item to be used in the next iteration to midpoint + 1, which means the next greater item to the item at the midpoint. Then the index of the array the next iteration will use starts from (midpoint + 1) and ends at the last index.

For example,

const searchTerm = 8;
const numbers = [ 1, 2, 4, 5,  7, 8, 9, 10, 12]

In the first iteration, our array index will start from 0 and ends at 8.

If the item at the midpoint (7) is less than what we are searching for (8), then the index of the array that will be used in the next iteration starts from (midpoint + 1) and ends at the last index. This process will be repeated until the item is found.

That is how to go about binary search algorithms.

Note: To remember how to handle the conditions in binary search, try to always remember this phrase “less than searchTerm go with first...greater than searchTerm go with last”.

Final code:

const searchTerm = 10;
const  numbers = [1,  3,  4,  6, 7, 8, 10, 14, 18, 50];

let firstIndex = 0
let lastIndex = numbers.length - 1;

for(let index = 0; index < numbers.length; index++ ) {

    const midpoint = (lastIndex + firstIndex) / 2;
    const itemAtMidpoint = numbers[midpoint];

    if ( searchTerm === itemAtMidpoint ) {
        console.log('found', itemAtMidpoint)
        return "Item is found";
    }

    if ( itemAtMidpoint > searchTerm ) {
        lastIndex = midpoint - 1;
    }

    if ( itemAtMidpoint < searchTerm ) {
         firstIndex = midpoint + 1;
    }
}

How to make the binary search algorithm a bit better?

Though binary search is faster than linear search whenever we have to look for an item from an array of items, both linear and binary search will not be appropriate if the array as a common difference of 1, eg.

const searchTerm = 4;
const numbers = [1,2,3,4,5,6,7,8,9,10]

We cannot use the binary search algorithm with the array above because the array has a common difference of 1. In this case, we can select the exact item we want without searching at all as in the below code:

const searchTermIndex = searchTerm - 1; //

The array has a common difference of 1 so we’re certain that it is exactly like the index of the array except that the array index starts from 0:

Numbers: 1,2,3,4,5,6,7,8,9,10 Indices: 0,1,2,3,4,5,6,7,8,9

If you look at the numbers and indices above, you will see that their difference is just 1, so were are sure the index of 4 is 4 - 1 = (3).

All we have to do is numbers[searchTermIndex] to get what we are searching for; Now, let’s make the binary search a bit better. Whenever an array has a common difference of 1, the algorithm should not use binary search, it should use random or exact search.

const searchTerm = 10;
const  numbers = [1,  3,  4,  6, 7, 8, 10, 14, 18, 50];

let firstIndex = 0
let lastIndex = numbers.length - 1;

for(let index = 0; index < numbers.length; index++ ) {
    const midpoint = (lastIndex + firstIndex) / 2;
    const itemAtMidpoint = numbes[midpoint];

    //code to make it better
    if ( searchTerm === numbers[searchTerm - 1] ) {
        console.log( "found", numbers[searchTerm - 1] )
        return "Item is found";
    }
    //

    if ( searchTerm === itemAtMidpoint ) {
        return "Item is found";
    }

    if ( itemAtMidpoint > searchTerm ) {
       lastIndex = midpoint - 1;
    }

    if ( itemAtMidpoint < searchTerm ) {
        firstIndex = midpoint + 1;
    }
}

Binary search time and space complexity

It is important to know how fast the binary search algorithms can be, so we are going to point to the best and worst-case time complexity.

The best-case time complexity of binary search

Binary search best case occurs whenever the element to be searched is at the midpoint of the list so the element is found in the first iteration and first comparison. Thus, O(1) is the best case of the binary search algorithm.

With the improvement I added to the binary search algorithm, its time complexity will always be O(1) whenever the elements of an array have a common difference of 1, eg. [1,2,3,4,5,6,7].

Worst-case time complexity of binary search algorithm

Binary search worst-case time complexity happens whenever the element to be searched is either has the first or the last index in the list. In this case, the time complexity is O(logN).

The space complexity of the binary search algorithm

The method of implementation determines the space complexity of the binary search algorithm. Its implementation by iteration has the space complexity of O(1) while its implementation by recursion has the space complexity of O(logN) because the recursion calls are stacked in the memory.

Conclusion

Binary search is an important algorithm used to search for an item in a list of items and we have covered how it is done. We have also improved it a bit. It is time you practise. Go now and use it.

Don’t forget: I am going to teach you how to answer common questions faanmg always ask from the binary search algorithm in another tutorial soon. See you then.