DSA & Implementation · core
Binary Search
Halving sorted search space, predicate search.
Mental model
Binary search is not about sorted arrays — it is about a monotonic predicate. If you can phrase the answer as "the smallest x for which condition(x) is true", you can binary-search the answer space, halving it each step.
How to study Binary Search
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use Binary search algorithm (Wikipedia) to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Binary Search with the neighboring concepts in its roadmap. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Search in a rotated sorted array, Binary Search and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Common mistakes
- Infinite loops from a wrong mid update or loop condition
- Searching values when you should search the answer space
- Integer overflow in `(lo + hi) / 2` — use `lo + (hi - lo) / 2`
Learn from primary sources
Practice and explain it back
Search in a rotated sorted array
A sorted array was rotated at an unknown pivot. Find a target's index in O(log n).
Expected evidence: search([4,5,6,7,0,1,2], 0) -> 4
Open the interactive drill →Binary Search
LeetCode #792 — Binary Search. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/binary-search/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Review prompts
- What property must hold before you can binary-search the answer space, and how do you check it?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.
Prerequisites
Related concepts
None assigned yet.