Algorithm Action: Binary Search

Photo by Clem Onojeghuo on Unsplash

Algos, algos, algos: the cornerstone of a competent software engineer. This is why I’m compiling all my research and work on the topic in a set of articles titled Algorithm Action.

Today, we’re checking out a specific sorting pattern known as binary search.

What is it?

Binary search is a much faster form of search. Instead of eliminating one element at a time, you eliminate half of the remaining elements each time a certain condition is met. The one caveat, however, is that binary search only works on sorted arrays. As such, it’s similar to the divide and conquer method I reviewed earlier in this series.

How does it work?

As I briefly mentioned in the last paragraph, binary works by elimination half the remaining elements in a sorted array every time a condition is met. Let’s see how we do this:

First, a function is defined that accepts an array and a value:

function binarySearch(arr, elem) {
}

Then we create a left and right pointer at the beginning and end of the array, along with determine the mid point of the array:

function binarySearch(arr, elem) {
    let start = 0; 
    let end = arr.length - 1; 
    let mid = Math.floor((start + end) / 2);
}

Now, onto the heart of binary search:

While the left pointer comes before the right pointer and the midpoint is value we’re looking for, return its index. If that mid value is too small, move the left pointer up. If the mid value is too big, move the right pointer down. And if you don’t find the value, return -1!

function binarySearch(arr, elem) {
let start = 0; 
    let end = arr.length - 1; 
    let mid = Math.floor((start + end) / 2);
if (sortedArr.length === 0) return -1;// EDGE CASE
while (arr[mid] !== elem && start <= end) { 
        if (elem < arr[mid]) { 
            end = mid - 1; 
        } else { 
            start = mid + 1; 
        }
        mid = Math.floor((start + end) / 2); 
    }
    
    if (sortedArr[mid] === elem) return mid
return -1
}

In terms of Big O, best is O(1), average is O(log n), and worst is O(log n)!

Thanks for reading!