How to write an iterative binary search algorithm in JavaScript

A step-by-step example to getting O(log n) speed for your iteration

Let’s say I handed you a dictionary and asked you to look up the definition for search. Then I asked you to the definition for binary. Would you start at about the same page for both?

Photo by Joshua Hoehne on Unsplash

I reckon for search you’d start somewhere a bit after the middle, and for binary, you’d start somewhere near the beginning. I reckon that because your efficient human brain learned early on that dictionaries are in alphabetical order, and to look for a word starting with “s” near the beginning was a waste of time.

Binary search attempts to bring a similar style of efficiency to searching for something. Let’s dive into an approach that, while iterative (I dive into the recursive version of this algorithm in this post), still accomplishes it in O (log n), which is considered highly efficient because, unlike common linear iteration, the number of operations to the size of the input decreases and tends to zero when the size of the input (n) increases. Let’s dive into an example below.

Imagine we had this sorted array of integers, and we needed to write a function that tells us if a given integer, let’s say lucky number 7, is in there or not:

arr = [1, 2, 4, 5, 7, 8, 9]

We can plainly see that it is. And a simple for loop would eventually reach 7 and return true. But what if we wanted to do it faster because the array was gynormous?

Let’s declare a function iterativeBinarySearch that takes in our array, and the number we’re searching. Let’s also declare two variables to help us in our task:

function iterativeBinarySearch(arr, n) {
  let start = 0;
  let end = arr.length - 1;
}

We initialize start at 0, and end at whatever the array’s length is minus 1. These two pointer variables will represent where we want our algorithm to focus at (sort of speak) as we iterate. We then enter a while loop, and immediately initialize a third variable that represents the midpoint between the start and end points:

function iterativeBinarySearch(n, arr) {
  let start = 0;
  let end = arr.length - 1;
while (start <= end) {
    let mid = Math.floor((start + end) / 2);
  }
}

Mid at this point is 3, because (0 + 6) / 2 = 3. The math.floor part is there to account for uneven cases. It will round down. We then immediately start looking for our inputed number, 7 in this case:

if (arr[mid] === n) {
      return true;
    }

Because arr[3] = 5, which ≠7, we don’t return true. We need an else:

else if (arr[mid] < n) {
      start = mid + 1;
    }

Because arr[mid] = 5, and 5 is less than 7, this statement evaluates to true, and re-assign the value of start to 4.

This is where the power of binary search begins.

If we know the middle point of what we’re looking for is less than the thing we’re looking for, why would we start looking all the way back near the beginning again? Let’s start from whatever the midpoint is, plus one.

We’re now back at the time of the while loop. We declare mid to be (3+1+6) / 2 = 5

• Because arr[5] = 8 ≠7, we don’t return true.
• Because arr[5] = 8 is not less than 7, we don’t return true either. But we haven’t found our number either. Turns out we need another else statement:

else {
      end = mid - 1;
    }

Similar to before, if we know the array at the midpoint is greater than the number we’re looking for, why would we look past this point again? Let’s make the end one less than the mid point. So now we make end 5–1 = 4.

We enter the loop again. Now our mid point is (4 + 4) / 2 = 4.

Because arr[4] = 7, which is the number we’re looking for, the statement now evaluates to true, and we return true. Here’s the full code for reference:

function iterativeBinarySearch(n, arr) {
  let start = 0;
  let end = arr.length - 1;
while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] === n) {
      return true;
    } else if (arr[mid] < n) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return false;
}

We found our number with only 3 iterations, as opposed to 4 that would’ve been with a normal for loop, which performs in linear time — O(n). With such a small array, this difference is trivial. But if our array was gigantor, continuously cutting the space we have to look through in half can make a significant difference. This fact is represented by the graph below: as the size of the object increases, the difference between an O(n) solution (the green line) and a O (log n) solution (the red line) widens. But with a low n, such as our example, the difference, if any , is negligible.

Thanks for reading!

And remember: grit > talent.