Unit 08
Searching Techniques
Finding a value is one of the most common operations in computing — and one decision, whether your data is sorted, completely changes how fast it can be.
// each comparison eliminates half of what's left to check
What it is
Searching means locating a target value within a collection. The two foundational approaches are linear search, which checks elements one by one, and binary search, which repeatedly halves the search space — but binary search only works on sorted data.
The two core approaches
- Linear search. Check every element in order until you find a match or reach the end. Works on any collection, sorted or not, but slow for large datasets.
- Binary search. Compare the target to the middle element; if it's smaller, search the left half, if larger, search the right half; repeat. Requires sorted data, but is dramatically faster.
Where each struggles
- Linear search doesn't scale — doubling the data roughly doubles the worst-case time.
- Binary search needs sorted data to begin with, and keeping data sorted as it changes has its own cost.
- Neither approach is ideal for "lookup by exact key" patterns where a hash table would do better — searching is most relevant when you need to check membership, find a position, or the data structure doesn't support hashing well (e.g. range queries on sorted data).
Time complexity
| Algorithm | Best | Worst | Requires sorted data? |
|---|---|---|---|
| Linear search | O(1) | O(n) | No |
| Binary search | O(1) | O(log n) | Yes |