Binary Search Patterns

🔹 Binary Search Patterns

Master these 5 patterns and you can solve 95% of binary search problems on LeetCode.

🗺️ Pattern Overview

#	Pattern	Trigger Phrase	Key Technique
1	Classic Search	”Find target in sorted array”	`lo <= hi`, return `mid`
2	First / Last Occurrence	”Find leftmost / rightmost X”	Don’t stop at match, keep shrinking
3	Search on Answer	”Minimum / maximum feasible value”	Binary search on answer range, not array indices
4	Rotated Sorted Array	”Sorted but rotated at unknown pivot”	Identify which half is sorted
5	Monotonic Function	”Find threshold where f(x) changes”	`lo < hi`, converge to boundary

🧭 Quick Decision Guide

What are you looking for?
│
├── Exact value in sorted array? ──────────→ Pattern 1 — Classic
├── First/last occurrence (duplicates)? ───→ Pattern 2 — Boundary
├── Min/max feasible value? ───────────────→ Pattern 3 — Answer Space
├── Rotated sorted array? ─────────────────→ Pattern 4 — Rotated
└── Monotonic/boolean threshold? ──────────→ Pattern 5 — Boundary

📋 When to Use Each Pattern

Problem Signals	Pattern
”Find value in sorted array”	Pattern 1 — Classic
”Find index of first/last X”	Pattern 2 — First/Last
Array has duplicates, find range	Pattern 2 — First/Last
”Minimum feasible X” / “Maximum X such that…”	Pattern 3 — Answer Space
”Allocate minimum resources to satisfy constraint”	Pattern 3 — Answer Space
Array is sorted but rotated	Pattern 4 — Rotated Array
Function is monotonically increasing/decreasing	Pattern 5 — Monotonic Function
”First version / day / point where condition changes”	Pattern 5 — Monotonic Function

📚 Learning Path

Step	Focus	File
1	Classic Search — The foundation	01-classic-search
2	First/Last Occurrence — Handling duplicates	02-first-last-occurrence
3	Search on Answer — Thinking beyond arrays	03-search-on-answer
4	Rotated Array — Sorted but twisted	04-rotated-array
5	Monotonic Function — The boundary finder	05-monotonic-function

Next: Pattern 1 — Classic Search →