Binary Search repeatedly cuts the search space in half.

The important skill is not memorizing code. It is recognizing what you are searching for and whether the search space is sorted or monotonic.

Sorted / Monotonic → Think Binary Search

---

Pattern Table

Pattern	Typical Questions	Keywords / Detection Cues	Main Idea
Classic Binary Search	Find target in sorted array	sorted, search, target	Search for a value
Lower / Upper Bound	First/last occurrence, insert position	first, last, position, range	Search for a boundary
Rotated Binary Search	Search rotated sorted array	rotated, pivot, sorted	Find the sorted half
Matrix Search	Search sorted matrix	matrix, row/column sorted	Flatten or staircase
Search on Answer	Min/max optimization	minimum, maximum, capacity, speed	Search possible answers

---

Mental Map

                    Binary Search
                         │
        ┌────────────────┼────────────────┐
        │                │                │
   Search Value      Search Boundary   Search Answer
        │                │                │
     Classic        Lower / Upper    Feasibility
        │                │                │
     Rotated        First / Last      Min / Max
        │
     Matrix

Master Mental Trigger

Ask: What am I searching?

Target value      → Classic
Boundary          → Lower / Upper Bound
Rotated array     → Rotated Binary Search
Matrix            → Matrix Search
Answer value      → Search on Answer

---

1. Classic Binary Search

When to Use

Use when:

• Array is sorted
• You need to find a specific value
• You want O(log n) search

Typical Questions

• Search target in sorted array
• Find whether an element exists
• Find index of a value

How It Works

Check middle
    ↓
Target = mid → Found
Target > mid → Search right
Target < mid → Search left

Mental Trigger

Sorted array + target → Classic Binary Search

Complexity

Time: O(log n)
Space: O(1)

---

2. Lower Bound / Upper Bound

Use Binary Search when you need a position/boundary, not just any matching element.

When to Use

Look for:

• First occurrence
• Last occurrence
• Insert position
• Count occurrences
• First element >= target
• First element > target

---

Lower Bound

Find the first position where value ≥ target.

Example

nums = [1, 2, 2, 2, 5]

target = 2

Lower Bound → index 1

Mental Trigger

First >= target → Lower Bound

---

Upper Bound

Find the first position where value > target.

Example

nums = [1, 2, 2, 2, 5]

target = 2

Upper Bound → index 4

Useful Relationships

First occurrence = Lower Bound

Last occurrence = Upper Bound - 1

Count of target =
Upper Bound - Lower Bound

Mental Trigger

Lower = first ≥ Upper = first >

---

3. Binary Search on Rotated Array

A rotated sorted array was sorted originally and then shifted.

Example:

Original:
[1, 2, 3, 4, 5, 6, 7]

Rotated:
[4, 5, 6, 7, 1, 2, 3]

When to Use

Look for:

• Rotated sorted array
• Pivot
• Search target after rotation
• Find minimum in rotated array

Key Observation

At least one half of the array is sorted.

How It Works

Find mid
   ↓
Which half is sorted?
   ↓
Is target inside that sorted half?
   ↓
Yes → search that half
No  → search the other half

Mental Trigger

Rotated → Find sorted half → Check target range

Complexity

Time: O(log n)
Space: O(1)

---

4. Binary Search on Matrix

There are two important cases.

---

A. Fully Sorted Matrix

Example:

1   3   5
7   9   11
13  15  17

The matrix can be treated like one sorted array.

When to Use

• Every row is sorted
• First element of a row is greater than the last element of the previous row
• Matrix behaves like a sorted 1D array

Mental Trigger

Fully sorted matrix → Flatten → Binary Search

Complexity

O(log(rows × cols))

---

B. Row + Column Sorted Matrix

Example:

1   4   7
2   5   8
3   6   9

Rows are sorted and columns are sorted, but the entire matrix is not one continuous sorted array.

Use Staircase Search.

How It Works

Start from the top-right corner.

value < target → move down

value > target → move left

Why?

• Moving left gives smaller values
• Moving down gives larger values

Mental Trigger

Rows + columns sorted → Staircase Search

Complexity

O(rows + cols)

---

5. Search on Answer

This is the most important Binary Search pattern where the input itself may not be sorted.

You binary search the possible answer values.

When to Use

Look for:

• Minimum capacity
• Minimum speed
• Minimum time
• Maximum distance
• Minimize maximum
• Maximize minimum
• “Minimum X such that…”
• “Maximum X such that…”

Key Question

Ask:

Can I check whether an answer X is possible?

If yes, and the result is monotonic, Binary Search may work.

---

Example Thinking

Suppose you need the minimum capacity.

Possible answers might look like:

10  20  30  40  50  60
❌  ❌  ❌  ✅  ✅  ✅

Once capacity 40 works, everything larger also works.

So:

Search the answer range
        ↓
Check if mid is feasible
        ↓
Feasible → try smaller
Not feasible → try larger

For Minimize

feasible → move left
not feasible → move right

For Maximize

feasible → move right
not feasible → move left

Mental Trigger

Numeric answer + feasibility check + monotonic → Search on Answer

---

Pattern Evolution

Classic Binary Search
        ↓
Sorted array
        ↓
Need a boundary?
        ↓
Lower / Upper Bound
        ↓
Array is rotated?
        ↓
Rotated Binary Search
        ↓
Matrix?
        ↓
Flatten / Staircase
        ↓
No sorted input but answer is numeric?
        ↓
Search on Answer

---

Common Mistakes

1. Searching the wrong thing

Always ask:

What is my search space?

Target       → Classic
Boundary     → Lower / Upper
Rotated      → Sorted half
Matrix       → Matrix positions
Answer       → Answer range

---

2. Confusing Lower and Upper Bound

Lower → first >= target

Upper → first > target

---

3. Using normal Binary Search on a rotated array

You cannot blindly compare target with mid.

First determine:

Which half is sorted?

---

4. Flattening every matrix

Flattening only works when the matrix is fully sorted row-major.

If only rows and columns are sorted:

Use Staircase Search.

---

5. Missing monotonicity in Search on Answer

Binary Search on Answer requires something like:

❌ ❌ ❌ ✅ ✅ ✅

or:

✅ ✅ ✅ ❌ ❌ ❌

If feasibility jumps randomly:

❌ ✅ ❌ ✅ ❌

Binary Search does not work.

---

Recognition Cheat Sheet

If you see…	Think…
Sorted array + target	Classic Binary Search
First >= target	Lower Bound
First > target	Upper Bound
First / last occurrence	Lower / Upper Bound
Rotated sorted array	Rotated Binary Search
Fully sorted matrix	Flattened Binary Search
Row + column sorted matrix	Staircase Search
Minimize maximum	Search on Answer
Maximize minimum	Search on Answer
Minimum speed/capacity/time	Search on Answer