DSA & Algorithms
Part 5 of 21 · DSA Interview PatternsBinary Search & Search-on-Answer — Predicates, Bounds & Feasibility
Classic binary search plus search-on-answer over monotonic feasibility predicates.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The predicate is monotonic
Prefer
Halve the search space
Classic search on a sorted array, or search on the answer when feasible(mid) goes from no to yes exactly once.
- Lower bound is the first index with value >= x.
- Search-on-answer multiplies a log by the cost of the check.
- lo + (hi - lo) // 2 avoids a fixed-width overflow story.
Alternative
Scan until you see it
Linear search hides the log factor the interviewer is waiting for.
- An infinite loop from an inconsistent mid update.
- A feasibility check you never proved is monotonic.
- Returning mid when the question wanted the first or last hit.
Halve, then move one side
The loop is the same. Only the meaning of mid changes.
- 1
Set lo and hi
Indexes, or the smallest and largest possible answers. - 2
Test mid
Equal, too small, or feasible. - 3
Keep the half that can still win
hi = mid when mid itself might be the answer.
Overview
Classic binary search plus search-on-answer over monotonic feasibility predicates.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use when the search space is monotonic: sorted array, or a yes/no feasible(mid) that flips once.
Recognition cues
- find target / first true / insertion point
- minimize maximum capacity / speed / days (search on answer)
- peak element in unimodal array
Mental model
Decisions
- 1
1. Set lo and hi
- next2. Pick mid
- 2
2. Pick mid
- next3. Is mid feasible?
- ?
3. Is mid feasible?
- no4. lo becomes mid + 1
- yes5. hi becomes mid
- 4
4. lo becomes mid + 1
- next6. lo still below hi?
- 5
5. hi becomes mid
- next6. lo still below hi?
- ?
6. lo still below hi?
- yes2. Pick mid
- no7. Answer is lo
- 7
7. Answer is lo
Lesson map
Binary Search & Search-on-Answer — Predicates, Bounds & Feasibility
Classic binary search plus search-on-answer over monotonic feasibility predicates.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB l["1. Set lo and hi"] m["2. Pick mid"] p["3. Is mid feasible?"] lo["4. lo becomes mid + 1"] l -->|1. Set lo and hi to 2. Pick mid| m m -->|2. Pick mid to 3. Is mid feasible?| p p -->|no| lo
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- O(log n) iterations over search space size.
- feasible cost multiplies (e.g. O(n) check → O(n log R)).
Common pitfalls & interview traps
LeetCode drill (real problems)
- Binary Search
- Search Insert Position
- Find First and Last Position of Element in Sorted Array
- Search in Rotated Sorted Array
- Capacity To Ship Packages Within D Days
- Koko Eating Bananas
- Median of Two Sorted Arrays
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Lower vs upper bound?
Answer
Lower is first index with value >= x; upper is first > x.
Search on answer?
Answer
Binary search the numeric answer; check feasibility in linear time.
Rotated array key?
Answer
One half is always sorted; decide which half holds the target.
Why hi = mid not mid-1?
Answer
When mid might still be the answer (minimize pattern).
Unimodal peak?
Answer
Compare mid to mid+1 to discard a half.
Duplicate first occurrence?
Answer
On match keep searching left: hi = mid.