This page documents the binary search pattern as implemented throughout the LeetCode problem solutions in the repository. Binary search is a fundamental algorithm pattern used to efficiently find elements or determine optimal values in sorted or monotonic search spaces with $O(\log n)$ time complexity.
This documentation covers:
For foundational binary search algorithm implementations and templates, see Binary Search Templates. For other algorithmic patterns like hash tables and sliding windows, see Hash Table Pattern and Sliding Window Pattern.
The repository documents binary search as finding boundaries rather than just searching sorted arrays. As stated in basic/searching/BinarySearch/README.md1-3: "二分的本质并非'单调性',而是'边界',只要找到某种性质,使得整个区间一分为二,那么就可以用二分把边界点二分出来" (The essence of binary search is not "monotonicity" but "boundary" - as long as you find a property that divides the entire interval in two, you can use binary search to find the boundary point).
The codebase provides two standard templates that maintain the answer within the binary search interval:
Template 1: Finding Left Boundary
Diagram: Template 1 Pattern Flow
Sources: basic/searching/BinarySearch/README.md8-24
Template 2: Finding Right Boundary
Used when the condition requires left = mid (see basic/searching/BinarySearch/README.md26-43):
Key Differences:
| Aspect | Template 1 | Template 2 |
|---|---|---|
| Mid calculation | (left + right) >> 1 | (left + right + 1) >> 1 |
| On check true | right = mid | left = mid |
| On check false | left = mid + 1 | right = mid - 1 |
| Use case | Find first position where condition is true | Find last position where condition is true |
Sources: basic/searching/BinarySearch/README.md8-54
Diagram: Binary Search Template Usage Across Problems
Sources: basic/searching/BinarySearch/README.md8-54 solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/Solution.java81-102 solution/0000-0099/0035.Search Insert Position/Solution.java89-101 solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.java140-148
The searchInsert() implementation in solution/0000-0099/0035.Search Insert Position/Solution.java89-101 follows Template 1:
Execution trace for nums = [1,3,5,6], target = 2:
| Iteration | l | r | mid | nums[mid] | Comparison | Action |
|---|---|---|---|---|---|---|
| Initial | 0 | 4 | - | - | - | - |
| 1 | 0 | 4 | 2 | 5 | 5 ≥ 2 | r = 2 |
| 2 | 0 | 2 | 1 | 3 | 3 ≥ 2 | r = 1 |
| 3 | 0 | 1 | 0 | 1 | 1 < 2 | l = 1 |
| End | 1 | 1 | - | - | l ≥ r | return 1 |
Sources: solution/0000-0099/0035.Search Insert Position/README.md74-85 solution/0000-0099/0035.Search Insert Position/Solution.java89-101
The searchRange() function in solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/Solution.java85-89 calls a search() helper twice:
Diagram: Double Binary Search Strategy in searchRange()
Sources: solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/Solution.java85-102
The search() helper implementation:
Key insight: search(target + 1) returns the first position where nums[mid] >= target + 1, which is one past the last occurrence of target.
Cross-Language Implementation Comparison:
| Language | Function | File Reference |
|---|---|---|
| Python | bisect_left() | solution/0000-0099/0034.../Solution.py3-5 |
| Java | search() helper | solution/0000-0099/0034.../Solution.java91-101 |
| C++ | lower_bound() | solution/0000-0099/0034.../Solution.cpp4-5 |
| Go | sort.SearchInts() | solution/0000-0099/0034.../Solution.go2-3 |
| Rust | search closure | solution/0000-0099/0034.../Solution.rs4-16 |
| TypeScript | search() function | solution/0000-0099/0034.../Solution.ts2-12 |
Sources: solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/README.md63-78 solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/Solution.java85-102
A powerful variation is binary search on answer, used when finding the minimum or maximum value that satisfies certain conditions. The pattern exploits monotonicity: if value v satisfies the condition, all values > v (for minimum problems) or < v (for maximum problems) also satisfy it.
Diagram: Binary Search on Answer Component Architecture
Sources: basic/searching/BinarySearch/README.md45-54 solution/1800-1899/1870.Minimum Speed to Arrive on Time/README.md84-96
The minSpeedOnTime() function in solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.java123-137 demonstrates binary search on answer using Template 1.
Code Structure Mapping:
The check() validation function at solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.java140-148:
Diagram: minSpeedOnTime() Function Call Flow
Sources: solution/1800-1899/1870.Minimum Speed to Arrive on Time/README.md84-96 solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.java123-148
The key decision is choosing between Template 1 and Template 2 based on the update direction:
Template Selection Rules (from basic/searching/BinarySearch/README.md45-54):
while (left < right)mid = (left + right) / 2right = mid, use Template 1 (no modification to mid)left = mid, use Template 2 (add +1 to mid calculation)Comparison Table:
| Problem Type | Template | Mid Calculation | Check Success Action | Example |
|---|---|---|---|---|
| Find first valid position | Template 1 | (l + r) >> 1 | r = mid | Problem 34, 35 |
| Find last valid position | Template 2 | (l + r + 1) >> 1 | l = mid | Maximum problems |
| Find minimum value | Template 1 | (l + r) >> 1 | r = mid | Problem 1870 |
| Find maximum value | Template 2 | (l + r + 1) >> 1 | l = mid | Problem 1898 |
Why Template 2 needs +1:
When left = mid is used, without the +1, the following scenario causes infinite loop:
left = 1, right = 2mid = (1 + 2) / 2 = 1left = mid = 1 → No progress!With +1:
mid = (1 + 2 + 1) / 2 = 2left = 2 → Loop exitsSources: basic/searching/BinarySearch/README.md45-54
Diagram: Binary Search Implementation Strategies by Language
Sources: solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/ solution/0000-0099/0035.Search Insert Position/
| Language | Function | Return Value | File Example |
|---|---|---|---|
| Python | bisect_left(a, x) | Index of leftmost position to insert x | solution/0000-0099/0034.../Solution.py3 |
| C++ | lower_bound(begin, end, val) | Iterator to first element ≥ val | solution/0000-0099/0034.../Solution.cpp4 |
| Go | sort.SearchInts(a, x) | Smallest index i with a[i] ≥ x | solution/0000-0099/0034.../Solution.go2 |
| Java | Arrays.binarySearch(a, key) | Index if found, else -(insertion point)-1 | solution/0000-0099/0035.../Solution.java254-256 |
Java - Explicit Helper Method:
From solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/Solution.java91-101:
TypeScript - Inline Function:
From solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/Solution.ts2-12:
Rust - Closure with Type Inference:
From solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/Solution.rs4-16:
Go - Function Literal:
From solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.go7-19:
Sources: solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/Solution.java91-101 solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/Solution.ts2-12 solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/Solution.rs4-16 solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.go7-19
Choosing the right binary search approach depends on the problem characteristics:
Problem Classification Examples:
| Problem | Type | Pattern Used | Key Feature |
|---|---|---|---|
| Problem 34 | Boundary Search | Double binary search | Finds both left and right |
| Problem 35 | Insertion Position | Left boundary | Standard lower_bound |
| Problem 1870 | Optimization | Binary search on answer (min) | Check function validates speed |
| Problem 1898 | Optimization | Binary search on answer (max) | Subsequence validation check |
Sources: solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/README.md solution/0000-0099/0035.Search Insert Position/README.md solution/1800-1899/1870.Minimum Speed to Arrive on Time/README.md solution/1800-1899/1898.Maximum Number of Removable Characters/README.md
All implementations use <FileRef file-url="https://github.com/doocs/leetcode/blob/86225ea1/left, right) where right is exclusive#LNaN-LNaN" NaN file-path="left, right)whereright` is exclusive">Hii
Java example from solution/0000-0099/0035.Search Insert Position/Solution.java94:
Why bit shift?
>>> 1 is equivalent to / 2 but faster(left + right) might overflow, but shift handles itleft + (right - left) / 2 (explicitly overflow-safe)Sources: solution/0000-0099/0035.Search Insert Position/Solution.java94 solution/0000-0099/0035.Search Insert Position/Solution.cpp6
From solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.java124-126:
Pattern: Validate problem constraints before entering binary search loop. For Problem 1870, if there are more trains than ceiling of available hours, it's impossible to complete the journey.
Sources: solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.java124-126
From solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.java129-130:
Key points:
return l > m ? -1 : l; checks if answer exceeds constraintSources: solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.java129-137
The check() function in binary search on answer must satisfy:
Properties Table:
| Property | Description | Example from Problem 1870 |
|---|---|---|
| Deterministic | Same input → same output | check(dist, v, hour) always returns same boolean for same parameters |
| Monotonic | If check(x) true, then check(x+k) true (or opposite for max) | If speed v works, speed v+1 also works |
| Efficient | O(n) or better | Iterate once through dist array |
| Correct boundary | Returns exactly the desired condition | s <= hour matches "arrive on time" |
Implementation from solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.java140-148:
Sources: solution/1800-1899/1870.Minimum Speed to Arrive on Time/Solution.java140-148
| Pattern | Complexity | Explanation |
|---|---|---|
| Basic binary search | $O(\log n)$ | Halves search space each iteration |
| Range search (both boundaries) | $O(\log n)$ | Two independent binary searches |
| Binary search on answer | $O(n \times \log m)$ | $\log m$ iterations, each with $O(n)$ check |
Where:
All implementations use $O(1)$ auxiliary space:
left, right, and mid pointersExample from Problem 1898:
Sources: solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/README.md67 solution/1800-1899/1870.Minimum Speed to Arrive on Time/README.md96 solution/1800-1899/1898.Maximum Number of Removable Characters/README.md89
Binary search solutions follow a consistent file structure:
solution/
├── 0000-0099/
│ ├── 0034.Find First and Last Position of Element in Sorted Array/
│ │ ├── README.md # Chinese documentation
│ │ ├── README_EN.md # English documentation
│ │ ├── Solution.py # Python implementation
│ │ ├── Solution.java # Java implementation
│ │ ├── Solution.cpp # C++ implementation
│ │ ├── Solution.go # Go implementation
│ │ ├── Solution.ts # TypeScript implementation
│ │ ├── Solution.rs # Rust implementation
│ │ ├── Solution.js # JavaScript implementation
│ │ └── ... # Other language implementations
│ └── 0035.Search Insert Position/
│ └── [same structure]
└── 1800-1899/
├── 1870.Minimum Speed to Arrive on Time/
│ └── [same structure]
└── 1898.Maximum Number of Removable Characters/
└── [same structure]
Documentation Structure:
二分查找, 数组) and difficultySources: solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/README.md1-8 solution/1800-1899/1870.Minimum Speed to Arrive on Time/README.md1-11
Refresh this wiki
This wiki was recently refreshed. Please wait 6 days to refresh again.