Pattern GuideBinary Search
Algorithm Pattern

Binary Search

"Divide and Conquer: Find the Needle by Halving the Haystack."

12 min read Intermediate Time: O(log N)
01
CORE INTUITION

The Power of Halving

📉

Eliminating the Impossible

Binary Search works because the search space is ordered. Instead of checking elements one by one (O(N)), we pick a midpoint, evaluate it, and eliminate half the remaining candidates in a single step. This yields O(log N) — in a sorted array of 1 billion items, you only need 30 comparisons.

The magic is the monotonic decision: at every step, the comparison tells you which half is guaranteed to be empty of answers. You never revisit discarded space.

Golden Rule: If the input is sorted or the problem hints at a monotonic condition (FFF...TTT), Binary Search should be your first instinct.

02
CLUES

Identifying the Pattern

Visual Cues

  • "Given a sorted array..."
  • "Search in O(log N) time complexity."
  • "Find the first or last occurrence."
  • "Array is rotated or has duplicates."

Optimization Cues

  • "Minimize the Maximum possible value."
  • "Maximize the Minimum possible distance."
  • "Find the threshold where condition X holds."
  • "Capacity / speed / threshold lies between [A, B]."
03
MINDSET

The Search Space

Think in terms of a shrinking interval, not an array. The answer must lie within [low, high]. Every step cuts the interval in half while preserving the invariant: the answer is still inside.

LOW
low
left boundary
DECISION
mid
test point
HIGH
high
right boundary

At each step, ask: "Is mid the answer? If not, which half must contain it?" — then move low or high past mid, never including it again.

04
STANDARD SEARCH

Exact Match

Find the exact value in a sorted array

LOW
2
1
5
2
8
3
12
MID
16
5
23
6
38
7
56
8
72
HIGH
91
Decision: Too Small → Move Low
1 / 3

How Standard Search Works

The classic algorithm. Given a sorted array and a target, repeatedly cut the search space in half by comparing the midpoint to the target.

Loop Invariant

If the target exists in the array, it is always within [low, high]. When low > high, the space is empty → target not found.

⚠ Overflow: Use low + (high - low) / 2 instead of (low + high) / 2 to avoid integer overflow in typed languages.

binary_search.js
1
function binarySearch(nums, target) {
2
let low = 0, high = nums.length - 1;
3
while (low <= high) {
4
let mid = low + Math.floor((high - low) / 2);
5
if (nums[mid] === target) return mid;
6
else if (nums[mid] < target) low = mid + 1;
7
else high = mid - 1;
8
}
9
return -1;
10
}
05
LOWER BOUND

First ≥ Target

How Lower Bound Works

Find the leftmost position where an element is ≥ target. Instead of returning -1 on miss, it returns the insertion point — the index where the target would go to maintain sorted order.

Key Insight

When nums[mid] >= target, the answer is at mid or to its left — so save mid as a candidate and keep searching left (high = mid - 1).

Also works for: First occurrence of target in a sorted array with duplicates.

lower_bound.js
1
function lowerBound(nums, target) {
2
let low = 0, high = nums.length - 1;
3
let ans = nums.length;
4
while (low <= high) {
5
let mid = low + Math.floor((high - low) / 2);
6
if (nums[mid] >= target) {
7
ans = mid;
8
high = mid - 1;
9
} else low = mid + 1;
10
}
11
return ans;
12
}
06
UPPER BOUND

First > Target

How Upper Bound Works

Find the leftmost position where an element is strictly > target. Identical to lower bound but uses > instead of >=.

Range Counting

Together, lower and upper bound give you the count of a value in a sorted array: count = upperBound(nums, target) - lowerBound(nums, target).

Also works for: Last occurrence of target (upper bound minus one).

upper_bound.js
1
function upperBound(nums, target) {
2
let low = 0, high = nums.length - 1;
3
let ans = nums.length;
4
while (low <= high) {
5
let mid = low + Math.floor((high - low) / 2);
6
if (nums[mid] > target) {
7
ans = mid;
8
high = mid - 1;
9
} else low = mid + 1;
10
}
11
return ans;
12
}
07
SEARCH ON ANSWER

The Predicate Pattern

The FFF...TTT strip

12 candidate values (1-12). Red = isPossible(x) is false, green = true. Binary search hunts for the boundary — the first green cell.

1
F
2
F
3
F
4
F
5
F
6
F
7
T
8
T
9
T
10
T
11
T
12
T

Search range: index 0 to 11 (values 1-12). Find the smallest value where isPossible(x) is true.

1 / 5

How Search on Answer Works

Instead of searching an array, you search a range of possible values. The array is replaced by a predicate function isPossible(x) that returns true when x is a valid answer.

The FFFTTT Boundary

The predicate must be monotonic: once it becomes true for some value, it stays true for all larger (or smaller) values. You are searching for the first T in the FFF...TTT sequence.

Minimize Max
If capacity C works, any C' > C also works. Find the smallest C that works.

Maximize Min
If distance D works, any D' < D also works. Find the largest D that works.

search_answer.js
1
function searchAnswer(rangeLow, rangeHigh) {
2
let low = rangeLow, high = rangeHigh;
3
let ans = -1;
4
while (low <= high) {
5
let mid = low + Math.floor((high - low) / 2);
6
if (isPossible(mid)) {
7
ans = mid;
8
high = mid - 1;
9
} else {
10
low = mid + 1;
11
}
12
}
13
return ans;
14
}
08
ROTATED

The Cliff Principle

A rotated sorted array is not one continuous slope — it's two separate ascending sequences separated by a Cliff (the pivot). Even in this broken landscape, at least one half is always perfectly sorted.

NAVIGATION RULES

  • Identify the "Clean" (Sorted) Half by comparing nums[low] to nums[mid].
  • If the target lies within the clean half's range, discard the messy half.
  • Otherwise, discard the clean half and search the messy side.

Example: [4, 5, 6, 7, 0, 1, 2] — left half [4, 5, 6, 7] is sorted, right half is messy. If target is 5, search left. If target is 1, search right.

search_rotated.js
1
function search(nums, target) {
2
let low = 0, high = nums.length - 1;
3
while (low <= high) {
4
const mid = low + Math.floor((high - low) / 2);
5
if (nums[mid] === target) return mid;
6
7
if (nums[low] <= nums[mid]) { // left half is sorted
8
if (nums[low] <= target && target < nums[mid]) high = mid - 1;
9
else low = mid + 1;
10
} else { // right half is sorted
11
if (nums[mid] < target && target <= nums[high]) low = mid + 1;
12
else high = mid - 1;
13
}
14
}
15
return -1;
16
}
09
MISTAKES

Interview Killers

Wrong Loop Condition

Using low < high instead of low <= high skips the final element when low === high. The invariant requires checking every candidate.

Infinite Loop from low = mid

When low + 1 === high, mid rounds down to low. If the condition keeps low = mid, the loop never terminates. Always use low = mid + 1 and high = mid - 1.

Overflow in mid

(low + high) / 2 can overflow in C++/Java when low + high exceeds INT_MAX. Use low + (high - low) / 2 — equivalent but safe.

Non-Monotonic Predicate

Search-on-Answer requires a monotonic predicate (FFF...TTT). If the predicate flips back and forth (TFTFT), binary search will return garbage.

10
PRACTICE

Ready to Practice?

Classic Binary SearchEasy
Find First and Last PositionMedium
Search in Rotated Sorted ArrayMedium
Koko Eating BananasMedium

"Binary Search = Maintain a shrinking valid interval using a monotonic decision."