Binary Search

A simple way to search for an element in an array is to traverse each element in the array until you find the target element. This can done by using a basic for loop to iterate through the array. While this approach is easy to implement it might not be the most optimal. When we are working with an array that is sorted in ascending or descending order there is much better method that can dramatically decrease our run time.

A common way of describing binary search is looking up someone in the phone book. If we were looking for Joe Smith we wouldn’t search every name starting from the beginning until we found Joe Smith. A more optimal approach would be to open the book to the middle and start from there. Say the middle brought us to last names starting with the letter M. We now know that we can disregard the first half of the book because Smith comes after M. We now take the last half of the book and once again find the middle. Say this brings us to the letter R. We once again disregard the first half of the remaining names, find the middle and repeat until we find Joe Smith.

To put the optimization of binary search into perspective let’s use the example of finding an element among a list of 1,000 entries. If we are using a simple traversal and the entries happened to be at the end of the list we would have to search through all 1,000 entries in a worst case scenario. Using binary search we reduce the number of searches to 10 in a worst case. That’s a dramatic decrease! First we take 1,000, cut it in half to 500. Then cut 500 to 250 and so forth. The larger the number of the original list grows the more efficient binary search becomes. Say we increased the number of elements from 1,000 to 1,000,000. This would only require 20 searches in a worst case.

Big O

If we were put this optimization in Big O terms we would say that we are reducing our worst case run time from O(n) to O(log n). A basic traversal could potentially require the iteration of every single element. Therefore the run time is increasing proportionally to the number of elements. With binary search the number of remaining elements is continually being halved so this is described as log2 n (logarithm to the power of 2), which is more commonly just referred to as “log n” in programming. This is basically the inverse of exponential growth.

Implementation

Here’s how we would implement binary search on an array in Javascript. First we would need to create 3 pointers. One at the beginning of the array, one at the end of the array, and one in the middle. The middle element can be calculated by adding the beginning and end pointers, dividing the sum by 2 and then using the Math.floor function to round the number down to the nearest integer.

From here we can use a while loop to check if the middle pointer has found the target element. If not then we check if the middle is greater than or less than the target. If it is greater we change the end pointer to the current middle value and subtract 1. If it is less we change the front pointer to the current middle value and add 1. We then recalculate the middle based on our new beginning and end pointers.

In this example we are returning the index of the target element if it is found or returning -1 if the array does not contain the target element.

Next time you are creating a function to search for an element in array and you have the luxury of dealing with a sorted array, use the approach to take advantage of the exponential decrease in run time.