CS Algorithms 101 – Binary Search

Binary search is a search algorithm used to find the position of a target value (or key) within a sorted array of values. It works by repeatedly dividing the search interval in half, eliminating the half that does not contain the target value, until the target value is found or determined to not exist in the array.

Here’s how a binary search algorithm typically works using vanilla JavaScript:

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

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

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

  return -1;
}

const arr = [1, 3, 5, 7, 9, 11];
const target = 7;

console.log(binarySearch(arr, target)); // output: 3

1. Initialize two pointers, left and right, to the first and last index of the array, respectively.
2. Calculate the middle index mid of the search interval by taking the average of left and right: mid = (left + right) / 2.
3. Compare the target value with the middle element of the array. If the target value is equal to the middle element, the search is complete and the index of the middle element is returned. If the target value is less than the middle element, discard the right half of the array and update right to be mid - 1. If the target value is greater than the middle element, discard the left half of the array and update left to be mid + 1.
4. Repeat steps 2 and 3 until the target value is found or left is greater than right. If left is greater than right, the target value does not exist in the array and -1 is returned.

The key advantage of binary search is that it has a logarithmic time complexity of O(log n), which is much faster than a linear search with a time complexity of O(n). However, it requires the array to be sorted beforehand, which may take additional time depending on the size of the array.