Finding a thing. The word covers two genuinely different activities, and keeping them apart is most of what this folder is for.

  1. 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.
  2. 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

  1. 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.
  2. 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.
  3. 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

StrategyFrontier is a…Finds
Linear search— (no frontier; just a scan)any match,
Binary search— (halving an interval)a match in a sorted collection,
BFSqueuefewest edges
DFSstacksome path, cheaply in memory
Uniform-cost / Dijkstramin-heap on cost-so-far lowest cost
Greedy best-firstmin-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.


↑ Back to Algorithms