Binary Search in JavaScript

Binary Search is one of the most basic algorithm that is studied by CS students. Questions about Binary Search are also very popular during coding interviews.

Binary Search is used when you need to efficiently locate a value in a sorted list of values. Rather than checking all the values one by one in a linear fashion, you can make use of the fact that the list is sorted and first check if the value you're looking for is in the middle of the list.

If not, then determine which half of the list may contain the value and start over again checking the middle of that sub-list.

var ar = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

var position = findNumber(90, ar);
println(position);

You are probably familiar with this algorithm if you played the "find the number game" in which one person picks a random number and you have to find it guided only by the hints the other player tells about the numbers you are trying.

In this short article, I will present you two simple implementations of Binary Search in JavaScript.

Solution 1: Recursive approach

// Find number n in sorted array ar
// Returns array index if found or -1 if not found
function findNumber(n, ar)
{
    return _findNumber(n, ar, 0, ar.length - 1);
}

// Find number n in sorted array ar in between indexes i1 and i2
// using recursive approach
function _findNumber(n, ar, i1, i2)
{
    if (i2 < i1)
        return -1;

    println("Checking interval: [" + i1 + ", " + i2 + "]");

    var mid = i1 + Math.floor((i2 - i1) / 2);

    if (n === ar[mid])
        return mid;

    if (n < ar[mid])
        return _findNumber(n, ar, i1, mid - 1);

    return _findNumber(n, ar, mid + 1, i2);
}

As you can see the recursive approach is very easy to implement. However, sometime an iterative approach is more efficient and therefore preferred over a recursive one.

Solution 2: Iterative approach

// Find number n in sorted array ar using iterative approach
// Returns array index if found or -1 if not found
function findNumber2(n, ar)
{
    var i1 = 0;
    var i2 = ar.length - 1;

    while(i1 <= i2)
    {
        println("Checking interval: [" + i1 + ", " + i2 + "]");

        var mid = i1 + Math.floor((i2 - i1) / 2);

        if (n === ar[mid])
            return mid;

        if (n < ar[mid])
        {
            i2 = mid - 1;
        }
        else
        {
            i1 = mid + 1;
        }
    }

    return -1;
}

You can find the full source code of this article in the playground from codeguppy.com

Direct link: https://codeguppy.com/code.html?Y5RZ5qiu1nVUiamySIz4