Coding Challenge Practice - Question 32

The task is to implement a Binary Search to find the index of a given array of unique and ascending integers.

The boilerplate code:

function binarySearch(arr, target){
  // your code here
}

A binary search algorithm is used to find the position of a target value within a sorted array.

To find the index, start by initializing the boundaries

let left = 0
let right = arr.length - 1

Left is 0, because arrays start from index 0. Right is the length of the array minus 1, because the index of the last item will be one short of the array's length.

While there's a valid range from left to right, compute the middle index and compare it to the target value

while (left <= right) {
const mid = ((left + right) / 2);
const midVal = arr[mid]

if (midVal === target) {
      return mid; // found it
    } else if (midVal < target) {
      left = mid + 1; // search right half
    } else {
      right = mid - 1; // search left half
    }
}

If the middle value is less than the target, ignore the left half of the array and search the right. If it is greater than the target, ignore the right side and search the left.

The final code

function binarySearch(arr, target){
  // your code here
  let left = 0;
  let right = arr.length - 1;

  while(left <= right) {
    const mid = Math.floor((left + right) / 2);
    const midVal = arr[mid];

    if(midVal === target) {
      return mid
    } else if(midVal < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return -1;
}

That's all folks!