The Binary Search Algorithm

Intro

I recently took a data structures and algorithms course as part of my pursuit to learn lower level programming and computer science concepts. As the saying goes, the best way of solidifying your knowledge in something is to teach it, and since I've already filled my quota for boring my partner with coding talk for the month (probably the year), I thought I'd write a series of posts with some of the things I've learned. This is one such post.

What is the Binary Search Algorithm

The binary search algorithm is an efficient way of returning the index of a given value in a sorted array. It has a worst-case time complexity of O(log n) where the element does not exist and a best-case time complexity of O(1) where the value we're searching for happens to be the first one we check!

How does it work

The idea behind the binary search algorithm is to divide and conquer. First, we check the mid point in the array. If the mid point is equal to the value we're looking for, we return the value. Otherwise, we divide the array in half and continue to look in the appropriate half and repeat the process. Remember, this only works on a sorted array.

Let's write some pseudo-code where v = the value we're looking for to further this explanation:

lo = 0
hi = arr.length
mid = (lo + hi) / 2

while lo < hi
    if mid = v
        we found it!

    if mid > v
        hi = mid

    if mid < v
        lo = mid

we didn't find it :(

Here we have 3 pointers; lo (set to the 1st element of the array), mid (set to the middle point of the array) and hi (set to the length of the array). We check the value of mid; if mid is the value we're looking for, then we're done! If mid is greater than our value, this means that the value we're looking for (if it exists) will be in the left half of our array. At this point, we move our hi pointer down to where our mid pointer is and we start the process again. If, however, mid is less than our value, then we move our lo pointer up to where our mid pointer is, and we start the process again.

How do we implement it

Here's some heavily commented Typescript:

function binarySearch(
  haystack: number[], 
  needle: number
): number {
    let lo = 0;
    let hi = haystack.length;

    do {
        const mid = Math.floor((hi + lo) / 2);
        const v = haystack[mid];

        if (v === needle) {
            return mid;
        } else if (v > needle) {
            hi = mid;
        } else {
            lo = mid + 1; // we can exclude mid as we've already checked it
        }
    } while (lo < hi);

    return -1;
}

This implementation obviously uses a do-while loop, but you can get the job done with any kind of loop, really. Alternatively, this is a good place to use recursion. Here's what a recursive version might look like:

function binarySearchRecursive(
    haystack: number[],
    needle: number,
    lo: number = 0,
    hi: number = haystack.length
): number {
    // Base case
    if (lo > hi) {
        return -1;
    }

    const mid = Math.floor((lo + hi) / 2);

    if (haystack[mid] === needle) {
        return mid; // We found it!
    }

    if (haystack[mid] < needle) {
        // recurse - search in the right half
        return binarySearchRecursive(haystack, needle, mid + 1, hi); 
    }

    if (haystack[mid] > needle) {
        // recurse - search in the left half
        return binarySearchRecursive(haystack, needle, lo, mid - 1); 
    }
}

I think we're done here

That's it for our binary search algorithm. I hope you found it useful or, at least, interesting!