Binary Search

Think of it like this

You're guessing a number between 1 and 1000. After each guess, you're told "higher" or "lower". The worst strategy: guess 1, then 2, then 3... (O(n)). The best strategy: guess 500 first. Either way, you've eliminated half the possibilities in one step. Then 750 or 250. And so on.

After 10 guesses, you've narrowed 1000 possibilities to 1. Because log₂(1000) ≈ 10.

This is binary search: eliminate half the search space at every step.

The Core Template (Find Exact Value)

The hardest part of binary search is getting the boundary conditions right. Here's a single template that works:

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
 
  while (left <= right) {
    // Use Math.floor((left + right) / 2) BUT:
    // In languages with int overflow (Java, C++), use:
    const mid = left + Math.floor((right - left) / 2);
 
    if (arr[mid] === target) return mid;       // found
    if (arr[mid] < target)   left  = mid + 1;  // target in right half
    else                     right = mid - 1;  // target in left half
  }
 
  return -1; // not found
}

Step through an example:

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91],  target = 23
 
Iteration 1: left=0, right=9, mid=4  → arr[4]=16 < 23  → left=5
Iteration 2: left=5, right=9, mid=7  → arr[7]=56 > 23  → right=6
Iteration 3: left=5, right=6, mid=5  → arr[5]=23 = 23  ✓ return 5
 
Only 3 iterations for 10 elements. log₂(10) ≈ 3.3 ✓

Binary Search (Target = 7)

1 / 3

[0]

↑ L

[1]

[2]

↑ M

[3]

[4]

[5]

↑ R

Mid is 5. Since 5 < 7, target must be in the right half.

Three Templates You Must Know

Most "tricky" binary search problems use leftmost or rightmost boundary variants:

// Template 1: Find exact target
// Use when: target must exist OR return -1
function findExact(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target)   left  = mid + 1;
    else                     right = mid - 1;
  }
  return -1;
}
 
// Template 2: Find leftmost position where condition is true
// Use when: "find first occurrence", "find minimum valid value"
// Condition: "is arr[mid] >= target?" (first element >= target)
function findLeftmost(arr, target) {
  let left = 0, right = arr.length; // right = arr.length (not -1!)
  while (left < right) {            // strict <, not <=
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < target) left  = mid + 1;
    else                   right = mid;  // mid might be the answer
  }
  return left; // left == right at termination; check arr[left] === target
}
 
// Template 3: Find rightmost position where condition is true
// Use when: "find last occurrence", "find maximum valid value"
function findRightmost(arr, target) {
  let left = 0, right = arr.length - 1;
  let result = -1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) { result = mid; left = mid + 1; } // save, keep looking right
    else if (arr[mid] < target) left  = mid + 1;
    else                        right = mid - 1;
  }
  return result;
}

Binary Search on a Rotated Array

A sorted array that's been rotated: [4, 5, 6, 7, 0, 1, 2]. Key insight: one half is always sorted — use that to determine which half contains the target.

function searchRotated(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;
 
    // Left half is sorted
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) right = mid - 1; // target in left
      else left = mid + 1;                                               // target in right
    }
    // Right half is sorted
    else {
      if (nums[mid] < target && target <= nums[right]) left = mid + 1; // target in right
      else right = mid - 1;                                             // target in left
    }
  }
  return -1;
}

Binary Search on the Answer (The Advanced Technique)

This is what separates good binary search knowledge from great. Instead of searching an array, you binary search the answer space — find the minimum or maximum value that satisfies a condition.

Pattern: "Minimum/Maximum X such that [condition]"

Condition must be monotonic:
  false, false, false, ... TRUE, TRUE, TRUE
 
Binary search to find the boundary.

Example: Koko Eating Bananas

"Piles of bananas. K hours. Find minimum eating speed S such that Koko can eat all bananas in ≤ K hours."

function minEatingSpeed(piles, h) {
  // Answer space: 1 (eat 1/hour, slowest) to max(piles) (eat whole pile in 1 hour)
  let left = 1, right = Math.max(...piles);
 
  while (left < right) {
    const speed = left + Math.floor((right - left) / 2);
    const hours = piles.reduce((sum, p) => sum + Math.ceil(p / speed), 0);
    if (hours <= h) right = speed; // speed works, try lower (find minimum)
    else            left  = speed + 1; // too slow, need more speed
  }
  return left;
}
 
// Why binary search? Monotonic condition:
// Speed 1:  takes 100 hours (too slow)
// Speed 10: takes 30 hours (too slow)
// Speed 50: takes 10 hours (works!) ← binary search finds this boundary
// Speed 100: takes 5 hours (works, but not minimum)

Example: Minimum Days to Make M Bouquets

function minDays(bloomDay, m, k) {
  if (m * k > bloomDay.length) return -1;
 
  function canMake(day) {
    let bouquets = 0, consecutive = 0;
    for (const d of bloomDay) {
      if (d <= day) { consecutive++; if (consecutive === k) { bouquets++; consecutive = 0; } }
      else consecutive = 0;
    }
    return bouquets >= m;
  }
 
  let left = 1, right = Math.max(...bloomDay);
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (canMake(mid)) right = mid;
    else              left  = mid + 1;
  }
  return left;
}

Real-World Frontend Application

Virtual scrolling: Given a scroll position (e.g., 3847px), binary search the cumulative height array to find which item index is at that position — O(log n) vs O(n) linear scan
Timestamp lookup: Binary search a sorted array of log timestamps to find the first entry after a given time — like filtering console logs in DevTools
Git bisect: Git's bisect command literally runs binary search on your commit history to find which commit introduced a bug
Range slider: Snap-to-value behavior in a numeric range input — binary search the valid tick positions array for the nearest value

Common Pitfalls (These Kill Interviews)

Pitfall	Code	Fix
Integer overflow	`mid = (left + right) / 2` (overflows in Java/C++)	`mid = left + (right - left) / 2`
Infinite loop	`left = mid` instead of `left = mid + 1`	Always move at least one step
Off-by-one: `<` vs `<=`	Wrong termination condition	Template 1 uses `left <= right`; Template 2 uses `left < right`
Wrong on rotated array	Treating rotated as sorted	Check which half is sorted, then decide
Forgetting to verify result	`arr[left]` might not be `target` after leftmost search	Always check `arr[left] === target` after Template 2

Time and Space Complexity

Variant	Time	Space
Standard binary search	O(log n)	O(1)
Binary search on answer	O(log(range) × f(n)) where f = cost to verify	O(1)
Recursive binary search	O(log n)	O(log n) call stack

Key Problems to Solve

#	Problem	Technique	Difficulty
1	Binary Search (basic)	Template 1	Easy
2	First Bad Version	Template 2 (leftmost)	Easy
3	Search Insert Position	Template 2	Easy
4	Find Minimum in Rotated Array	Rotated binary search	Medium
5	Search in Rotated Sorted Array	Rotated with target	Medium
6	Find Peak Element	Binary search on condition	Medium
7	Koko Eating Bananas	Binary search on answer	Medium
8	Capacity to Ship Packages	Binary search on answer	Medium
9	Split Array Largest Sum	Binary search on answer	Hard
10	Median of Two Sorted Arrays	Partition-based binary search	Hard

function binarySearch(arr, target) { let left = 0, right = arr.length - 1; while (left <= right) { // Use Math.floor((left + right) / 2) BUT: // In languages with int overflow (Java, C++), use: const mid = left + Math.floor((right - left) / 2); if (arr[mid] === target) return mid; // found if (arr[mid] < target) left = mid + 1; // target in right half else right = mid - 1; // target in left half } return -1; // not found }

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target = 23 Iteration 1: left=0, right=9, mid=4 → arr[4]=16 < 23 → left=5 Iteration 2: left=5, right=9, mid=7 → arr[7]=56 > 23 → right=6 Iteration 3: left=5, right=6, mid=5 → arr[5]=23 = 23 ✓ return 5 Only 3 iterations for 10 elements. log₂(10) ≈ 3.3 ✓

// Template 1: Find exact target // Use when: target must exist OR return -1 function findExact(arr, target) { let left = 0, right = arr.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (arr[mid] === target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } // Template 2: Find leftmost position where condition is true // Use when: "find first occurrence", "find minimum valid value" // Condition: "is arr[mid] >= target?" (first element >= target) function findLeftmost(arr, target) { let left = 0, right = arr.length; // right = arr.length (not -1!) while (left < right) { // strict <, not <= const mid = left + Math.floor((right - left) / 2); if (arr[mid] < target) left = mid + 1; else right = mid; // mid might be the answer } return left; // left == right at termination; check arr[left] === target } // Template 3: Find rightmost position where condition is true // Use when: "find last occurrence", "find maximum valid value" function findRightmost(arr, target) { let left = 0, right = arr.length - 1; let result = -1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (arr[mid] === target) { result = mid; left = mid + 1; } // save, keep looking right else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return result; }

function minEatingSpeed(piles, h) { // Answer space: 1 (eat 1/hour, slowest) to max(piles) (eat whole pile in 1 hour) let left = 1, right = Math.max(...piles); while (left < right) { const speed = left + Math.floor((right - left) / 2); const hours = piles.reduce((sum, p) => sum + Math.ceil(p / speed), 0); if (hours <= h) right = speed; // speed works, try lower (find minimum) else left = speed + 1; // too slow, need more speed } return left; } // Why binary search? Monotonic condition: // Speed 1: takes 100 hours (too slow) // Speed 10: takes 30 hours (too slow) // Speed 50: takes 10 hours (works!) ← binary search finds this boundary // Speed 100: takes 5 hours (works, but not minimum)

function minDays(bloomDay, m, k) { if (m * k > bloomDay.length) return -1; function canMake(day) { let bouquets = 0, consecutive = 0; for (const d of bloomDay) { if (d <= day) { consecutive++; if (consecutive === k) { bouquets++; consecutive = 0; } } else consecutive = 0; } return bouquets >= m; } let left = 1, right = Math.max(...bloomDay); while (left < right) { const mid = left + Math.floor((right - left) / 2); if (canMake(mid)) right = mid; else left = mid + 1; } return left; }

Pitfall

Code

Fix

Integer overflow

mid = (left + right) / 2 (overflows in Java/C++)

mid = left + (right - left) / 2

Infinite loop

left = mid instead of left = mid + 1

Always move at least one step

Off-by-one: < vs <=

Wrong termination condition

Template 1 uses left <= right; Template 2 uses left < right

Wrong on rotated array

Treating rotated as sorted

Check which half is sorted, then decide

Forgetting to verify result

arr[left] might not be target after leftmost search

Always check arr[left] === target after Template 2

Variant

Time

Space

Standard binary search

O(log n)

O(1)

Binary search on answer

O(log(range) × f(n)) where f = cost to verify

O(1)

Recursive binary search

O(log n)

O(log n) call stack

Problem

Technique

Difficulty

Binary Search (basic)

Template 1

Easy

First Bad Version

Template 2 (leftmost)

Easy

Search Insert Position

Template 2

Easy

Find Minimum in Rotated Array

Rotated binary search

Medium

Search in Rotated Sorted Array

Rotated with target

Medium

Find Peak Element

Binary search on condition

Medium

Koko Eating Bananas

Binary search on answer

Medium

Capacity to Ship Packages

Binary search on answer

Medium

Split Array Largest Sum

Binary search on answer

Hard

Median of Two Sorted Arrays

Partition-based binary search

Hard

Binary Search

Binary Search#

Think of it like this

The Core Template (Find Exact Value)

Binary Search (Target = 7)

Three Templates You Must Know

Binary Search on a Rotated Array

Binary Search on the Answer (The Advanced Technique)

Real-World Frontend Application

Common Pitfalls (These Kill Interviews)

Time and Space Complexity

Key Problems to Solve

Binary Search

Binary Search#

Think of it like this

The Core Template (Find Exact Value)

Binary Search (Target = 7)

Three Templates You Must Know

Binary Search on a Rotated Array

Binary Search on the Answer (The Advanced Technique)

Real-World Frontend Application

Common Pitfalls (These Kill Interviews)

Time and Space Complexity

Key Problems to Solve

Binary Search

Binary Search