Searching Practice Problems
How to Use This Problem List
Searching problems reduce to exactly three root techniques: linear scan when unsorted, binary search on a sorted array when looking for a value, and binary search on an answer space when looking for a minimum or maximum that satisfies a condition.
The challenge is pattern recognition — knowing which of the three applies within the first two minutes of reading. The recognition clue column in each table gives the exact phrase that triggers the technique.
Practice one pattern at a time. After four or five problems from the same pattern, the recognition becomes automatic.
Pattern 1: Linear Search and Variants
The foundation. Used when the array cannot be sorted, when you need the first element satisfying a predicate, or when the input is too small to justify more complex approaches.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Find the Index of the First Occurrence in a String | Easy | "find first occurrence of needle in haystack" | Slide a window of needle length across haystack |
| Search in a 2D Matrix (unsorted rows) | Medium | "matrix rows not sorted globally" | Flatten to 1D mentally and scan — or smarter: start top-right |
| Find All Numbers Disappeared in Array | Easy | "find missing numbers in range [1,n]" | Mark visited using negation — linear scan |
| Contains Duplicate | Easy | "does array have duplicates" | HashSet membership — O(n) with O(n) space |
| Missing Number | Easy | "find missing from [0,n]" | XOR or Gauss formula — O(n) time O(1) space |
| Find the Duplicate Number | Medium | "one number repeated, range [1,n]" | Floyd's cycle detection — O(n) O(1) |
| First Bad Version | Easy | "first bad version in range" | Binary search on version range — but listed here as base |
| Single Element in Sorted Array | Medium | "every element appears twice except one" | XOR entire array — O(n) O(1); also solvable with binary search |
Complexity target: O(n) time, O(1) or O(n) space depending on approach.
Recognition signal: "find first element where", "unsorted array", "range [1,n] with missing/duplicate", "no sorting possible". Any problem where sorting cannot be assumed or applied.
Pattern 2: Classic Binary Search — Sorted Array
Standard binary search and its direct variants. These problems are solvable with the exact template from the binary search page: lo <= hi, mid = lo + (hi-lo)/2, return index or -1.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Binary Search | Easy | "find target in sorted array" | Direct template — lo, hi, mid, return index |
| Search Insert Position | Easy | "find index or insertion point" | Binary search; return lo when not found — that is the insertion point |
| Count Occurrences of Target | Easy | "count how many times target appears" | first_occurrence + last_occurrence → count = last - first + 1 |
| Find Smallest Letter Greater Than Target | Easy | "next letter in circular sorted array" | Binary search; wrap with modulo |
| Fixed Point in Array | Easy | "find index i where arr[i] == i" | Binary search on i — arr[i] < i → search right; arr[i] > i → search left |
| Find K Closest Elements | Medium | "k elements closest to x in sorted array" | Binary search for x, then expand two-pointer outward |
| Sqrt(x) — Integer Square Root | Easy | "floor of square root without sqrt()" | Binary search on [1, x/2]; mid² ≤ x → result = mid; lo = mid+1 |
| Valid Perfect Square | Easy | "is n a perfect square without sqrt()" | Binary search for exact mid² == n |
| Guess Number Higher or Lower | Easy | "guess number with higher/lower feedback" | Direct binary search — API is the comparison function |
Complexity target: O(log n) time, O(1) space.
Recognition signal: "sorted array", "find target", "find insertion position", "O(log n) search". The array is explicitly sorted or the problem domain is ordered.
Pattern 3: Lower Bound and Upper Bound
Binary search variants that find the leftmost or rightmost position of a value — or the boundary between two conditions. These are the building blocks for range queries and count problems.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Find First and Last Position of Element | Medium | "first and last occurrence of target in sorted array" | Lower bound for first, upper bound - 1 for last |
| Count of Range Sum | Hard | "count subarrays with sum in [lower, upper]" | Merge sort or sorted structure + upper_bound - lower_bound |
| H-Index | Medium | "maximum h where h papers have ≥ h citations" | Binary search on sorted citations; condition: citations[n-h] ≥ h |
| Online Election | Medium | "find leading candidate at time t" | Binary search on sorted times to find latest ≤ t |
| Time-Based Key-Value Store | Medium | "get value at or before timestamp" | Store sorted timestamps per key; binary search for ≤ t |
| Find Right Interval | Medium | "for each interval, find smallest start ≥ end" | Sort starts; binary search for each end |
| Maximum Distance in Arrays | Medium | "maximum element minus minimum across arrays" | Track running min/max with linear scan — optional lower bound |
| Count of Smaller Numbers After Self | Hard | "for each element, count elements to its right that are smaller" | Merge sort or BIT + binary search for position |
Complexity target: O(log n) per query, O(n log n) for preprocessing.
Recognition signal: "first occurrence", "last occurrence", "count in range", "closest without exceeding", "latest timestamp ≤ t". Any problem requiring the boundary between two conditions.
Pattern 4: Binary Search on Rotated Arrays
A sorted array that has been rotated at some pivot. Exactly one of the two halves is always fully sorted — use it to decide which half to search.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Search in Rotated Sorted Array | Medium | "find target in rotated sorted array" | One half always sorted; check if target in sorted half → search it; else search other |
| Search in Rotated Sorted Array II | Medium | "rotated array may have duplicates" | When arr[lo]==arr[mid]==arr[hi]: lo++, hi-- to skip duplicates |
| Find Minimum in Rotated Sorted Array | Medium | "find minimum in rotated sorted array" | arr[mid] > arr[hi] → min in right; else min in left or at mid |
| Find Minimum in Rotated Sorted Array II | Hard | "rotated with duplicates" | Skip duplicates at boundaries; same core logic |
| Number of Rotations | Easy | "how many times array was rotated" | Index of minimum element = number of rotations |
| Find Pivot Index in Rotated Array | Medium | "find rotation point / pivot" | Binary search for the minimum — its index is the pivot |
| Check if Array is Sorted and Rotated | Easy | "is array a sorted array rotated k times" | Count number of descent points — at most 1 |
Complexity target: O(log n) time, O(1) space.
Recognition signal: "rotated", "sorted then rotated", "cyclic shift". The array was sorted then some prefix was moved to the end — one half is always fully sorted.
Pattern 5: Binary Search on Answer Space
The problem does not ask for an index — it asks for a value (minimum speed, maximum capacity, minimum days, etc.). Binary search on the range of possible answers, with a feasibility check as the comparison function.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Koko Eating Bananas | Medium | "minimum speed to finish all piles in h hours" | lo=1, hi=max(piles); canFinish(k) = sum(ceil(p/k)) ≤ h |
| Capacity to Ship Packages in D Days | Medium | "minimum ship capacity to deliver in d days" | lo=max(w), hi=sum(w); canShip(c) simulates days needed |
| Minimum Number of Days to Make Bouquets | Medium | "minimum days to make m bouquets of k adjacent flowers" | Binary search on days; count bouquets bloomable by that day |
| Find the Smallest Divisor | Medium | "smallest divisor so sum of ceiling quotients ≤ threshold" | lo=1, hi=max(arr); condition: sum(ceil(a/d)) ≤ threshold |
| Magnetic Force Between Balls | Hard | "place balls to maximise minimum distance" | Sort positions; binary search on min distance; canPlace greedy check |
| Split Array Largest Sum | Hard | "split array into m parts minimising maximum subarray sum" | lo=max, hi=sum; canSplit(mid) counts if parts needed ≤ m |
| Allocate Books | Hard | "allocate books to students minimising maximum pages" | Same pattern as split array: lo=max(pages), hi=sum |
| Minimum Time to Repair Cars | Medium | "minimum time so all n cars repaired with given mechanics" | Binary search on time; for time t, count total cars repaired ≤ n |
| Kth Smallest Number in Multiplication Table | Hard | "kth smallest in m×n multiplication table" | Binary search on value; count values ≤ mid using floor(mid/i) |
| Find Kth Smallest Pair Distance | Hard | "kth smallest absolute difference among all pairs" | Sort; binary search on distance; count pairs ≤ mid with sliding window |
Complexity target: O(n log(range)) where range = hi - lo.
Recognition signal: "minimum X such that we can", "maximum X such that condition holds", "minimize the maximum", "maximize the minimum". The answer is a numeric value with a clear range, and there is a monotonic feasibility check.
Pattern 6: Binary Search in Special Structures
Binary search applied to 2D matrices, infinite arrays, and implicit sorted structures where the standard template applies with modified index arithmetic.
| Problem | Difficulty | Recognition Clue | Key Insight |
|---|---|---|---|
| Search a 2D Matrix | Medium | "row-sorted, first element of each row > last of previous" | Treat as flat sorted array: row = mid/cols, col = mid%cols |
| Search a 2D Matrix II | Medium | "each row and column sorted" | Start top-right: eliminate row (move down) or column (move left) |
| Find Peak Element II (2D Grid) | Hard | "find peak in 2D — greater than all 4 neighbours" | Binary search on columns; find row max in each column |
| Find in Sorted Matrix (Zigzag) | Medium | "matrix with zigzag sorted rows" | Decide per-row direction; binary search per row |
| Kth Smallest Element in Sorted Matrix | Medium | "kth smallest in row/col sorted matrix" | Binary search on value; count elements ≤ mid row by row |
| Search in a Sorted Infinite Array | Medium | "sorted array with unknown size" | Exponential search to find bounds, then binary search |
| Sqrt(x) for Reals | Easy | "square root to N decimal places" | Float binary search; 100 iterations for precision |
Complexity target: O(log(m×n)) for 2D matrix, O(n log(max)) for value-based.
Recognition signal: "sorted matrix", "row and column sorted", "find in 2D", "infinite sorted array". Sorted structure with non-linear indexing.
Recommended Study Order
Week 1 — Core Binary Search Pattern 1 (Linear): Missing Number, Find Duplicate, Contains Duplicate Pattern 2 (Classic): Binary Search, Search Insert Position, Sqrt(x) Week 2 — Boundary Problems Pattern 3 (Bounds): First and Last Position, Time-Based Key-Value Store Pattern 4 (Rotated): Search in Rotated Array, Find Minimum in Rotated Array Week 3 — Answer Space Pattern 5 (Answer): Koko Eating Bananas, Ship Packages, Magnetic Force Between Balls Pattern 5 (Hard): Split Array Largest Sum, Allocate Books Week 4 — Advanced Structures Pattern 6 (Matrix): Search a 2D Matrix, Kth Smallest in Sorted Matrix Mixed: Find Kth Smallest Pair Distance, Median of Two Sorted Arrays Revisit rotated array with duplicates
Problem-Solving Checklist for Searching Problems
Before writing code, answer these questions:
1. Is the array sorted (or can it be sorted)?
→ Yes, target is a value → Binary search on array (Pattern 2, 3, 4)
→ Yes, but rotated → Rotated binary search (Pattern 4)
→ No → Linear search (Pattern 1)
2. Is the answer a value in a range, not an index?
→ "minimum X such that condition holds" → Answer-space BS, hi = mid
→ "maximum X such that condition holds" → Answer-space BS, result = mid; lo = mid+1
→ (Pattern 5)
3. What does the condition check?
→ Write feasibility(mid) BEFORE binary search
→ Verify it is monotonic: all below threshold fail, all above pass
→ If not monotonic → binary search does not apply
4. Which template?
→ Finding an index (target present/absent): lo <= hi; return -1 if not found
→ Finding first valid (lower bound): lo < hi; hi = mid; return lo
→ Finding last valid (upper bound): lo < hi; lo = mid; return hi (or result pattern)
5. What are the correct lo and hi?
→ Answer space: lo = smallest possible (never exclude real answer)
hi = largest possible (never miss the real answer)
→ Array index: lo = 0; hi = n - 1 (inclusive)
6. Edge cases:
→ Empty array → return -1 immediately
→ Single element → does the template handle it?
→ All elements identical in rotated array → duplicates need lo++, hi--
→ Overflow in mid*mid or days calculation → use long/64-bit
Pattern Recognition Quick Reference
| Signal in Problem | Pattern | Template |
|---|---|---|
| "sorted array", "find target" | Classic binary search | lo <= hi; return index or -1 |
| "first occurrence", "last occurrence" | Lower/upper bound | hi = mid or lo = mid + 1; return result |
| "insertion point", "search insert" | Lower bound | lo < hi; return lo |
| "rotated sorted", "rotation point" | Rotated array BS | Identify sorted half; check if target in it |
| "minimum in rotated" | Rotated minimum | arr[mid] > arr[hi] → min in right; else left |
| "minimum X such that feasible" | Answer-space (min) | hi = mid when feasible |
| "maximum X such that feasible" | Answer-space (max) | result = mid; lo = mid + 1 when feasible |
| "minimize the maximum sum/load" | Answer-space (min) | Feasibility = simulate with given max value |
| "maximize the minimum distance" | Answer-space (max) | Feasibility = greedy placement check |
| "kth smallest in sorted matrix" | 2D binary search | Binary search on value; count ≤ mid per row |
| "sorted matrix rows and columns" | 2D elimination | Start top-right; eliminate row or column |
| "unsorted, find first satisfying" | Linear search | Sequential scan with predicate |
Difficulty Progression Reference
| Stage | Characteristics | Representative Problems |
|---|---|---|
| Foundation | Direct template, single condition | Binary Search, Sqrt(x), Search Insert Position |
| Early Intermediate | Boundary variants, first/last | First and Last Position, Find Minimum Rotated |
| Intermediate | Rotated search, simple answer space | Search Rotated Array, Koko, Ship Packages |
| Late Intermediate | Multi-condition answer space, 2D | Split Array, Allocate Books, Search 2D Matrix II |
| Advanced | Combined patterns, duplicates, hard bounds | Kth Smallest Pair Distance, Median Two Arrays, Rotated with Duplicates |
Common Interview Topics by Company Focus
Product-based companies (FAANG-tier):
- ›Search in Rotated Sorted Array — almost universal
- ›Koko Eating Bananas — canonical answer-space problem
- ›Find Minimum in Rotated Sorted Array — follow-up to rotation
- ›Median of Two Sorted Arrays — the hard binary search benchmark
- ›First and Last Position — lower/upper bound fundamentals
- ›Kth Smallest in Sorted Matrix — 2D binary search
Service-based and on-campus:
- ›Binary Search, Search Insert Position — direct application
- ›Find Duplicate / Missing Number — linear scan tricks
- ›Sqrt(x), Valid Perfect Square — numerical binary search
- ›Count Occurrences — first + last occurrence combined
Startup and mid-size tech:
- ›Time-Based Key-Value Store — practical lower bound application
- ›Capacity to Ship Packages — real-world answer-space modelling
- ›Find Peak Element — no sorted array binary search
- ›Magnetic Force Between Balls — maximise minimum distance
Progress Tracking
After solving each problem, record:
- ›Pattern — which of the 6 patterns does this belong to?
- ›Template used —
lo <= hi(index search) orlo < hi(bound/answer)? - ›lo and hi — what were the initial bounds and why?
- ›Condition — what does
condition(mid)check? Is it monotonic? - ›Edge case missed — empty array? Overflow? Duplicates in rotated?
- ›Time to solve — target 20-25 minutes for medium problems under interview conditions
The decisive indicator that pattern recognition is working: when you read "minimum speed to finish all tasks" and immediately think "answer-space binary search, lo=1, hi=max, condition=simulate and check", before reaching the constraints section.
A problem says 'find the minimum speed such that all work is done in time'. Which binary search variant do you use?