Here is a common JavaScript interview question:

Given an array of n integers sorted in ascending order, how quickly can we find if a given integer is in the array?

There are three ways to solve it that I can think of.

Cheating!

The new includes() method makes this quite simple.

const arr = [1,2,3,4,5];
arr.includes(2); // true
arr.includes(7); // false

But let’s assume we can’t use this approach.

Brute Force

We can iterate through the entire array to find our integer. This takes O(n) time in the worst case.

// O(n) time & O(1) space
function findNum(arr, n) {
  for (let i=0; i<arr.length; i++){
    if (arr[i] === n) {
      return true;
    }
  }
  return false;
}

If the list was not sorted we could solve this in O(n log n) time by first sorting the list O(log n) and then iterating over it O(n).

But it’s already sorted! So we can use binary search to solve this in O(log n) time.

How does binary search work again?

  1. Start with the middle number mid. If n > mid then return the section of the array larger than mid. Otherwise return the section less than mid.
  2. We’ve cut our problem size in half!
  3. Repeat this approach of starting in the middle and dividing the remaining array into half under we find the number or determine it’s not in the array.
// O(log n) time & O(1) space
function binarySearch(arr, n) {
  let min = 0,
      max = arr.length - 1,
      guess;

  while (min <= max) {
    guess = Math.floor((min + max) / 2);

    if (arr[guess] === n) {
      return true;
    } else {
      if (arr[guess] < n) {
        min = guess + 1;
      } else {
        max = guess - 1;
      }
    }
  }

  return false;
}



Want to improve your JavaScript? I have a list of recommended JavaScript books.