Binary Search Explained

Binary search is one of the most important algorithms in computer science. It finds a target value in a sorted array by repeatedly halving the search space. Time complexity: O(log n). It transforms O(n) linear scans into O(log n) logarithmic lookups.

How Binary Search Works

Maintain two pointers (left and right) that define the search space. At each step, check the middle element. If it matches, return it. If the target is smaller, search the left half. If larger, search the right half. Repeat until the search space is empty.

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

graph TD
    Start["binarySearch(arr, target)"]
    Check{"left <= right?"}
    Mid["mid = left + right / 2"]
    Match{"arr[mid] == target?"}
    Found["return mid"]
    GoRight{"arr[mid] < target?"}
    Left["left = mid + 1"]
    Right["right = mid - 1"]
    NotFound["return -1"]

    Start --> Check
    Check -->|"No"| NotFound
    Check -->|"Yes"| Mid
    Mid --> Match
    Match -->|"Yes"| Found
    Match -->|"No"| GoRight
    GoRight -->|"Yes"| Left
    GoRight -->|"No"| Right
    Left --> Check
    Right --> Check

    style Start fill:#D97A2B,stroke:#B86418,color:#fff
    style Check fill:#D97A2B,stroke:#B86418,color:#fff
    style Match fill:#D97A2B,stroke:#B86418,color:#fff
    style GoRight fill:#D97A2B,stroke:#B86418,color:#fff
    style Found fill:#D4EDDA,stroke:#28A745
    style NotFound fill:#F8D7DA,stroke:#DC3545
    style Left fill:#FAF6EE,stroke:#E8DFC8
    style Right fill:#FAF6EE,stroke:#E8DFC8
    style Mid fill:#FAF6EE,stroke:#E8DFC8

Why (right - left) / 2 + left?

Using (left + right) / 2 can cause integer overflow when left and right are large. left + (right - left) / 2 is mathematically equivalent but avoids overflow.

Variations

First Occurrence

Find the first position of target in a sorted array with duplicates.

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

Search in Rotated Array

A sorted array rotated at some pivot. One half is always sorted : check which half, then decide where to search.

Binary Search on Answer

When the answer space is monotonic (e.g., minimum capacity to ship packages in D days), binary search on the answer instead of the array. Check if a given answer is feasible, then narrow the range.

Common Mistakes

• Infinite loop: Using left = mid or right = mid without care. Always use left = mid + 1 or right = mid - 1 when the element is not a match.
• Off-by-one: The loop condition (<= vs <) and mid calculation must be consistent. With left <= right, use right = mid - 1.
• Not sorted: Binary search only works on sorted data. Verify the input is sorted before applying it.
• Integer overflow: Always use left + (right - left) / 2 instead of (left + right) / 2.
• Not considering the edge case: What if the array has one element? What if the target is smaller than all elements?