Why This Matters
Search is the act of spending computation to reduce uncertainty. Sometimes the target is an array element. Sometimes it is a graph path, a game state, a feasible schedule, or a dynamic-programming subproblem.
Core Idea
Use the structure you have:
| Structure | Search method |
|---|---|
| unsorted array | linear search |
| sorted array | binary search |
| unweighted graph distance | BFS |
| reachability or backtracking | DFS |
| weighted graph | priority-queue search |
Worked example: finding a name in an unsorted list is . If the list is sorted and random access is available, binary search reduces it to comparisons.
Common Mistakes
- Using binary search without sortedness.
- Using DFS when shortest unweighted path is required.
- Forgetting that building an index can cost more than one search is worth.
Exercises
- Pick the right search method for a sorted array, an unsorted list, and a maze.
- Explain why BFS finds shortest paths only when edges are unweighted.
- State when preprocessing for search is justified.
Next Topics
References
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 2, 20, 22.
- Skiena. The Algorithm Design Manual (3rd ed., 2020). Ch. 7.