The Binary Search algorithm is quite efficient and much faster with time complexity. It works on Divide and Conquer approach which eliminates roughly half of the elements of an array in every step until we find the one we are after. We will take a look at this in details below.

One thing to note is that the Binary Search algorithm only works with the sorted array so if the array is not sorted, we cannot use the Binary search.

Let’s take a look at the problem first and go through the walkthrough. After that, let’s write the solution and find its time and space complexity.

Problem

Write a function using the Binary Search algorithm which accepts a sorted array and a target value. The function should return the index at which the target value exists, otherwise -1.

Input

const array = [0, 1, 5, 10, 23, 32, 45, 67, 77, 80, 93, 103];
const target = 10;

Output

Binary Search walkthrough

The Binary Search algorithm sets the left and right pointer from the array and iterates until the left pointer equals or bigger than the right pointer. In the loop, it calculates the middle pointer using the left and right pointer and check if the value of the middle pointer matches the given target value.

If the value of the middle pointer doesn’t match with the target value, we move either left or right pointer depending whether the target value is bigger/smaller than the left/right pointer (at this step, the half of the elements will be eliminated), and we calculate the middle pointer again and check if it matches the target value.

This is the general walkthrough of how the Binary Search algorithm works. Now let’s go through each step for the above problem in more details.

1st loop

First we set the left pointer at the start of the array and the right pointer at the end of the array.

So from the problem, the left pointer will be index 0 and the right pointer will be index 11. From the left and right pointer, we calculate the middle pointer (rounding down) which is index 5 and the value of the middle pointer is 32.

Now we check if the value of the middle pointer, 32, matches the target value, 10. As it doesn’t match, now we check if the target value, 10, is bigger or smaller than the value of the middle pointer, 32. As 10 is smaller than 32, we move the right pointer to the middle index - 1 which will be index 4 and that eliminates the half of the array values.

2nd loop

We calculate the middle pointer with the left and new right pointer and it will be index 2.

As the middle pointer value, 5, doesn’t match with the target value 10 and the target value is bigger than the middle pointer value, this time we move the left pointer to the middle index + 1 which is index 3.

3rd loop

The middle pointer will be index 3.

As the middle pointer value, 10, matches with the target value , 10, this time we return the middle pointer value.

An example of returning `-1`

Now let’s change the target value to 17 and see how it continues from the 3rd loop.

As the target value is bigger than the middle pointer value, we move the left pointer to index 4.

4th loop

We calculate the middle pointer and it’s 4.

As the middle pointer value doesn’t match with the target value and the target value is smaller than the middle pointer value, we move the right pointer to index 3.

Now as the left pointer is bigger than right pointer, we will get out of the loop and return -1.

This is how the Binary Search algorithm works. With that in mind, let’s solve the problem.

Solution

The code below is the completed code.

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;
  
  while(left <= right) {
    const middle = Math.floor((left + right) / 2);

    if (target === array[middle]) {
      return middle;
    } else if (target < array[middle]) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  
  return -1;
}

Let’s start with declaring a function called binarySearch() which accepts the sorted array and the target value.

function binarySearch(array, target) {

}

To begin with, let’s set the left pointer to 0 which is the first index of the array and the right pointer to array.length - 1 which is the last index of the array.

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;
}

We will loop while the left pointer is less than or equal to the right pointer.

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while(left <= right) {
    ...
  }
}

In the loop, we will calculate the middle pointer in the middle of the array between the left and right pointer. We will round down (Math.floor) the middle pointer value.

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while(left <= right) {
    const middle = Math.floor((left + right) / 2);
  }
}

If the middle pointer value matches the target value, we will return the index of the middle pointer.

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while(left <= right) {
    const middle = Math.floor((left + right) / 2);

    if (target === array[middle]) {
      return middle;
    }
  }
}

If the middle pointer value doesn’t match the target value, we will check if the target value is smaller than the middle pointer value. If so, we move the right pointer to the one index before the middle pointer.

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while(left <= right) {
    const middle = Math.floor((left + right) / 2);

    if (target === array[middle]) {
      return middle;
    } else if (target < array[middle]) {
      right = middle - 1;
    }
  }
}

Otherwise, we can assume that the target value is bigger than the middle pointer value, so we will move the left pointer to one index bigger than the middle pointer.

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while(left <= right) {
    const middle = Math.floor((left + right) / 2);

    if (target === array[middle]) {
      return middle;
    } else if (target < array[middle]) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
}

If none is satisfied and the left pointer gets bigger than the right pointer, we will return -1.

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;

  while(left <= right) {
    const middle = Math.floor((left + right) / 2);

    if (target === array[middle]) {
      return middle;
    } else if (target < array[middle]) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }

  return -1;
}

Big O

The time complexity of the Binary Search algorithm is O(log(n)) because we get rid of the half of the input on every step.

To test it, let’s add the console.log and see how many steps the Binary Search algorithm runs.

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;
  let steps = 1;

  while(left <= right) {
    console.log(steps);
    const middle = Math.floor((left + right) / 2);

    if (target === array[middle]) {
      return middle;
    } else if (target < array[middle]) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }

    steps++;
  }

  return -1;
}

We are going to create the worst case scenarios that the target value is not in the array.

Now when we send

8 elements, it will run 4 steps
16 elements, it will run 5 steps
32 elements, it will run 6 steps

which show O(log(n)).

The space complexity is O(1) because we don’t use any additional memory to store variables.