Learning Outcome
Handle exact search, lower_bound, upper_bound, and rotated sorted arrays with one invariant-first mindset.
Pattern Recognition
| Item | Detail |
|---|---|
| Core signal | The input is sorted, almost sorted, rotated, infinite, or asks for first/last valid position. |
| Use when | A sorted or monotonic property lets you eliminate half of the remaining search space. |
| Avoid when | The required invariant is not monotonic or the input constraints point to a simpler direct scan. |
Intuition
Every binary search bug is an invariant bug; decide whether mid is still a candidate before moving boundaries.
Exact Practice Question Names
- Search in Rotated Sorted Array
- Find First and Last Position of Element in Sorted Array
- Search Insert Position
- Find Position of Element in Infinite Sorted Array
- Median of Two Sorted Arrays
Interview Approach
- Use safe mid calculation.
- For boundary search, keep mid when it can still be the answer.
- For rotated search, identify the sorted half first.
- For infinite arrays, expand the range before binary search.
Pseudocode
while left < right:
mid = left + (right - left) // 2
if condition(mid) is true:
right = mid
else:
left = mid + 1
return leftSample Dry Run
In [4,5,6,7,0,1,2], mid=7. The left half is sorted. If target is 0, it is not in [4..7], so search the right half.
Edge Cases
- Single element
- Two elements
- Target absent
- Duplicates if the variant allows them
Common Mistakes
- Mixing first-true and exact-search templates
- Dropping mid even though it can be the answer
- Ignoring duplicates in rotated array follow-ups
Complexity
| Item | Detail |
|---|---|
| Expected time | O(log n) for standard variants; O(log answer + log n) for infinite array expansion. |
| Expected space | O(1). |
Java, C++ and Python Notes
- Java: prefer explicit classes and clear helper methods over clever one-liners.
- C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
- Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.
Quick Revision Checklist
- Name the pattern before coding.
- State the invariant or DP state in one sentence.
- Dry-run the smallest non-trivial example.
- Close with time and space complexity.