core pattern

Binary Search

Divide and conquer on sorted data. Repeatedly halve the search space by comparing the middle element. Works on sorted arrays, rotated arrays, or any monotonic function.

Time

O(log n)

Space

O(1)

🧠Mental Model

“Number guessing game — "higher" or "lower" eliminates half the possibilities each time.”

Verbal cue: Calculate mid, compare, halve the search space

🎯Recognition Triggers

When you see these patterns in a problem, consider this approach:

Sorted array searchFind boundary (first/last occurrence)Rotated sorted arraySearch insert positionMinimize/maximize with constraintSquare root, nth rootPeak element

📝Code Template

Binary Search Template

1function binarySearch(arr, target) {
2  let left = 0;
3  let right = arr.length - 1;
4  
5  while (left <= right) {
6    const mid = left + Math.floor((right - left) / 2);
7    
8    if (arr[mid] === target) {
9      return mid;
10    } else if (arr[mid] < target) {
11      left = mid + 1;
12    } else {
13      right = mid - 1;
14    }
15  }
16  
17  return -1;  // Not found
18}

Complexity rationale: Search space halves each iteration: n → n/2 → n/4 → ... → 1

💡Interview Tips

1Always mention the array must be sorted (or have monotonic property)
2Explain your loop invariant: "target is always in [left, right]"
3For boundary problems, continue searching even after finding target
4Binary search on answer space is a powerful technique for optimization

⚠️Common Mistakes

✕Integer overflow: (left + right) / 2 — use left + (right - left) / 2
✕Infinite loop: forgetting to move left or right by 1
✕Off-by-one: left <= right vs left < right depends on problem
✕Not recognizing binary search applies to answer space, not just arrays