Algorithms Lesson 10: Binary Search

Binary search eliminates half the search space with each step — finding a value in 1M sorted items takes only 20 comparisons. It’s the most underestimated algorithm.

Classic Binary Search

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;  // found!
    else if (arr[mid] < target) left = mid + 1;   // search right
    else right = mid - 1;                          // search left
  }
  return -1;  // not found
}

// O(log n) — finds in 1M items in 20 steps!

Binary Search on Answer

// Problem: Find square root of n (integer part)
function sqrt(n) {
  if (n < 2) return n;
  let left = 1, right = Math.floor(n / 2);
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (mid * mid === n) return mid;
    else if (mid * mid < n) left = mid + 1;
    else right = mid - 1;
  }
  return right;  // floor of sqrt
}

// Key insight: binary search works on ANY monotonic function!
// Not just arrays — also on function outputs (search the "answer space")

Find First and Last Position

function firstPosition(arr, target) {
  let left = 0, right = arr.length - 1, result = -1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) { result = mid; right = mid - 1; } // keep searching left
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return result;
}