Binary Search

Efficient searching in sorted arrays using divide and conquer

Overview

Searches sorted data by comparing with the middle element and reducing the search range each step.

Time	Space
O(log(n))	O(1)

Binary Search only works when the data is sorted.

Implementation

Iterative

Iterative Binary Search

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) {
      left = mid + 1;
    } else if (arr[mid] > target) {
      right = mid - 1;
    } else {
      return mid;
    }
  }

  return false;
}

console.log(binarySearch([-6, -2, 0, 2, 3, 3, 5, 7, 12], 5)); // 6

Recursive

Recursive Binary Search

function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return false;
  }

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

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

console.log(binarySearch([-6, -2, 0, 2, 3, 3, 5, 7, 12], 5)); // 6