Search

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:

Worked example: finding a name in an unsorted list is $O(n)$. If the list is sorted and random access is available, binary search reduces it to $O(\log n)$ 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

• Dynamic programming
• Greedy algorithms
• Divide and conquer

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.