← Index

Searching & Sorting

Binary Search

Find a value in a sorted array by halving the search space each step.

What it is

Binary search only works on sorted data, but when it applies, it's dramatically faster than scanning: check the middle element, and eliminate half the remaining array based on whether the target is bigger or smaller. O(log n) means doubling the input size only costs one extra comparison.

Real-world examples

• Guessing a number 1-100 with 'higher/lower' feedback — always guess the midpoint, and you'll never need more than 7 guesses.
• Flipping open a physical dictionary toward roughly where a word should be, then narrowing left or right, instead of reading page by page.

Where you've probably used this already

• git bisect — finding which commit introduced a bug by testing the midpoint of a commit range, repeatedly.
• Sorted database indexes (B-trees) resolve WHERE clauses using this exact halving idea instead of a full table scan.
• Autocomplete/typeahead over a pre-sorted dataset, or implementing 'insert into sorted position' efficiently.

Complexity

Code

// Binary Search — find a value in a SORTED array in O(log n) by
// repeatedly cutting the search space in half.

function binarySearch(sortedArr, target) {
  let low = 0;
  let high = sortedArr.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) {
      low = mid + 1; // target is in the right half
    } else {
      high = mid - 1; // target is in the left half
    }
  }
  return -1; // not found
}

// --- Recursive version, same idea ---
function binarySearchRecursive(sortedArr, target, low = 0, high = sortedArr.length - 1) {
  if (low > high) return -1;
  const mid = Math.floor((low + high) / 2);
  if (sortedArr[mid] === target) return mid;
  if (sortedArr[mid] < target) {
    return binarySearchRecursive(sortedArr, target, mid + 1, high);
  }
  return binarySearchRecursive(sortedArr, target, low, mid - 1);
}

// --- Example Usage ---
const nums = [1, 3, 5, 7, 9, 11, 13, 15];
console.log("Find 9:", binarySearch(nums, 9));   // 4
console.log("Find 2:", binarySearch(nums, 2));   // -1
console.log("Recursive find 13:", binarySearchRecursive(nums, 13)); // 6

// You use this shape of thinking constantly without a raw array:
// - Array.prototype.findIndex-style needs O(n), but a sorted DB index
//   lookup (B-tree) is doing binary search under the hood, O(log n)
// - "git bisect" to find which commit introduced a bug
// - autocomplete/typeahead over a sorted dataset