Part IX — Searching Algorithms
SummaryOverview of linear and binary search strategies, when...
Overview of linear and binary search strategies, when...
Overview of linear and binary search strategies, when to apply each, and how binary search extends beyond sorted arrays to optimization problems.
Searching Algorithms
Every program searches for something. A web server looks up routes. A database finds rows matching a query. An autocomplete widget hunts for prefix matches. Searching is so fundamental that the difference between an O(n) scan and an O(log n) lookup can determine whether your system handles ten users or ten million.
In interviews, searching questions test two things: your knowledge of algorithms and your ability to recognize which search strategy fits the problem. Picking the wrong one wastes time. Picking the right one signals that you think before you code.
Two Families of Search
Searching algorithms fall into two broad families based on what they assume about the data.
Linear search makes no assumptions. It examines every element in sequence until it finds the target or exhausts the collection. It works on unsorted arrays, linked lists, streams — anything iterable. The cost is O(n), and no clever trick can beat that lower bound when the data has no structure to exploit.
Binary search exploits order. Given a sorted array (or any monotonic predicate), it eliminates half the remaining candidates with each comparison. The cost drops to O(log n) — searching a billion elements takes roughly 30 steps instead of a billion. That logarithmic factor is one of the most powerful ideas in computer science.
The decision between them is straightforward:
| Condition | Strategy |
|---|---|
| Data is unsorted and you can’t sort it first | Linear search |
| Data is sorted or you can sort it once and search many times | Binary search |
| Data structure has no random access (linked list, stream) | Linear search |
| Collection is tiny (< 20 elements) | Linear search (lower constant overhead) |
| You need ALL matches, not the first one | Linear scan |
| The problem has a monotonic “feasibility” property | Binary search on answer |
That last row is the one that surprises candidates. Binary search applies not only to sorted arrays but to any problem where you can define a predicate that flips from false to true at some threshold. Finding the minimum speed to finish a task in time? Binary search on the speed. Minimizing the maximum load across workers? Binary search on the load. This “binary search on answer” paradigm shows up in dozens of interview problems, and mastering it sets you apart.
Beyond Arrays
Binary search extends to:
- Rotated sorted arrays — the array is sorted but pivoted at an unknown index, and you still achieve O(log n).
- 2D matrices — treat a sorted matrix as a flattened sorted array via index arithmetic.
- Abstract predicates — “first bad version,” “peak element,” and capacity-planning problems all reduce to binary search over a boolean function.
Linear search also plays roles you would not expect. It is the inner loop of insertion sort, the naive phase of string matching, and the fallback when data arrives as a stream you cannot revisit.
What’s Ahead
This part contains two sub-chapters:
- Linear Search — Sequential scan, sentinel optimization, complexity analysis, and the scenarios where linear search is your best (or only) option.
- Binary Search — Exact match, lower/upper bounds, the “search on answer” paradigm, rotated arrays, 2D matrix search, and a bulletproof strategy for eliminating off-by-one errors.
Work through both. Linear search grounds your understanding of lower bounds and brute-force baselines. Binary search gives you the logarithmic superpower that interviewers expect you to wield fluently. Together, they form the searching toolkit you need for every coding interview.