Binary Search in JavaScript

Binary search is an extremely useful and popular algorithm used for quickly searching in a sorted array. Binary search is even used by people in real life (outside of programming) when they play the guess the number game. One person thinks a number between 1 and 100, and the other person tries to guess. The response is only less, equal or greater. If you guess 50 and get a less response, you just narrowed down the search to half the interval, 1 to 50. You can keep going and guess 25. No matter if what answer you get, you either win, or narrow down the interval again to a half. This is how binary search works. We test our searched value against the element in the middle, if it’s less than the middle element, we repeat the process on the left part, if it’s greater than the middle element, we repeat the process on the right part. We repeat this until we get a value which is equal, at which point the search is complete.

The initial requirement is that the array must be sorted. Why? Because a sorted array has a simple property. If we take any two indexes i and j, if i <= j, then array[i] <= array[j]. This means if we know that the searched number is lower than the number at the middle index, its index must be also lower.

To implement to algorithm we will use two variables to store the bounds of our search area, low and high. We begin by setting low = 0 and high = array.length. We calculate the middle as the average of low and high, always rounding down using the Math.floor function. Note that we could also use a bitwise shift to the right with the >> operator to achieve the same, but we’ll keep the division explicit to make things easier to read. We then compare the number at the middle index to our search value. Here we can run into three different cases:

• If array[mid] < value, then we need to move to the right, updating our lower bound low = mid + 1. We add the one because the value can’t possibly be at mid (since it’s greater than array[mid]), so we can skip that index entirely.
• If array[mid] > value, then we need to move to the left, updating our upper bound high = mid. Since we initialize our high to array.length, the search range does not include the high index (it’s a left-closed interval), which means we don’t need to subtract 1 from the upper bound.
• If array[mid] == value, we simply return the mid index as a result.

We keep iterating until low == high, at which point the search is narrowed down to a single element which must be the result if the element was initially present.

function binarySearch(array, value) {
    var low = 0;
    var high = array.length;

    while (low < high) {
        var mid = Math.floor((low + high) / 2);

        if (array[mid] < value) {
            low = mid + 1;
        } else if (array[mid] > value) {
            high = mid;
        } else {
            return mid;
        }
    }

    return high;
}

Lastly, it’s important to note that if we search for an element which is not present in our array, we still get an index as a return value. There are two ways to think about this. Either we think of the binarySearch function as searching for an index of an existing element inside the array, at which point we might want to return -1 in case the element isn’t found. Or we use it to calculate an index at which we should insert a new element into the array so that it remains sorted.

If we wanted the first variant, we could modify the binary search to check the result value before returning it.

function binarySearch(array, value) {
    var low = 0;
    var high = array.length;

    while (low < high) {
        var mid = Math.floor((low + high) / 2);

        if (array[mid] < value) {
            low = mid + 1;
        } else if (array[mid] > value) {
            high = mid;
        } else {
            return mid;
        }
    }

    if (array[high] == value) {
        return high;
    } else {
        return -1;
    }
}

Alternatively, we can use the first implementation to implement an insert into a sorted array which uses binary search to find the right place to insert the value. This is rather trivial, we simply find the proper index with the first version of our binarySearch, and then use Array.splice to insert the new value.

The original code is provided here again so that the example as a whole can be copy-pasted into a developer console (or any other JavaScript environment) for experimentation.

function binarySearch(array, value) {
    var low = 0;
    var high = array.length;

    while (low < high) {
        var mid = Math.floor((low + high) / 2);

        if (array[mid] < value) {
            low = mid + 1;
        } else if (array[mid] > value) {
            high = mid;
        } else {
            return mid;
        }
    }

    return high;
}

function binaryInsert(array, value) {
    var index = binarySearch(array, value);
    array.splice(index, 0, value);
}

var arr = [1, 2, 3];

binaryInsert(arr, 2);
console.log(arr);
// [1, 2, 2, 3]

binaryInsert(arr, 5);
console.log(arr);
// [1, 2, 2, 3, 5]

binaryInsert(arr, 0);
console.log(arr);
// [0, 1, 2, 2, 3, 5]

Time complexity

The main benefit of binary search is its time complexity, which is only \(O(\log n\), compared to regular linear search (going through the whole array searching for the right index), which is \(O(n)\). Searching 1000000 elements using binary search would only take roughly 20 steps while it could take up to 1000000 steps.

But why is it \(O(\log n)\)? Each iteration of binary search reduces the search space by half, which means we can translate the question how many steps does it take? to how many times can we take a half of a number until we get to 1? If the array length was a power of two, meaning we could write it as \(2^k\), we could divide it by 2 exactly k times. If we have an arbitrary number n and we want to write it as \(2^k\), we can calcualte k with a logarithm, specifically \(\log_2 n = k\). But by the definition of the big-O notation, we don’t need to worry about constants, and since \(\log_2 n = \frac{\log n}{\log 2}\), we can simply use \(O(\log n)\).