Finding a thing. The word covers two genuinely different activities, and keeping them apart is most of what this folder is for.
- Searching a collection. You have a container of values and you want one of them. The question is how few elements you can get away with looking at. Answer: all of them if the data is unordered, and of them if it is sorted. This is linear and binary search.
- Searching a space. There is no container. There is a starting state, a rule for generating the states reachable from it, and a goal test — and the “collection” is generated as you go, is usually enormous, and may be infinite. Chess positions, puzzle configurations, route planning, and every implicit graph are this. The question is not “how few elements” but “which state to expand next”.
Both are called search. Only the second one has a frontier, a heuristic, or a reason to care about tie-breaking.
The lessons
- Linear and Binary Search — [Beginner → Intermediate] — the fallback and the payoff for sorting first; Python’s
bisect; the three classic binary-search bugs, each demonstrated failing, including the overflow that sat in the JDK for nine years. - Binary Search on the Answer — [Intermediate] — the move that makes binary search apply where there is no sorted array in sight: search the space of possible answers, using a monotone predicate as the comparison. Both templates, why they round the midpoint differently, and how to prove monotonicity before trusting it.
- State-Space Search — [Intermediate → Advanced] — the general frame: states, successors, the frontier, the explored set, duplicate detection, cost functions, heuristics and tie-breaking. One search function; the frontier’s container selects the algorithm — and tree search costs 60× more than graph search by depth 10.
How the searches relate
| Strategy | Frontier is a… | Finds |
|---|---|---|
| Linear search | — (no frontier; just a scan) | any match, |
| Binary search | — (halving an interval) | a match in a sorted collection, |
| BFS | queue | fewest edges |
| DFS | stack | some path, cheaply in memory |
| Uniform-cost / Dijkstra | min-heap on cost-so-far | lowest cost |
| Greedy best-first | min-heap on estimate-to-goal | fast, but not necessarily the best |
| A* | min-heap on | lowest cost, expanding fewer nodes than Dijkstra |
Read down the last four rows and only one thing changes: what the priority queue is keyed on. That is the payoff of treating these as one family rather than five algorithms.
Question banks
One bank per lesson: micro-questions with the answers hidden behind toggles, for closed-book recall rather than reading. Method explained in the arrays bank.
Related
- Sorting — what you do first to make binary search possible, and when that trade pays
- Graph traversal — BFS and DFS, the uninformed search strategies
- Graph algorithms — Dijkstra and A*, the informed ones
- Modified binary search — the pattern layer above lessons 01 and 02
- A\* — the informed strategy of lesson 03, in full
- 03-algorithms — the parent folder
Jump to a subject
Software engineering
Infrastructure & security
Computer science
Hardware & engineering