Finding an element in a collection, and the cost difference sorting buys you.
Searching asks whether a value is in a collection and where. The right method depends on one question: is the data sorted (or indexed)? If not, you scan; if it is, you can halve the problem at each step.
Linear search checks each element in turn. It needs no preparation, works on any iterable and any equality test, and is the fastest option for very small arrays because it is simple and cache-friendly. Binary search requires sorted, random-access data. It compares the target with the middle element and discards half the range each time, so a million items need about 20 comparisons. Python's bisect module implements it, and the same idea underlies B-tree indexes in databases.
| Method | Best | Average | Worst | Space | Requires |
|---|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) | Nothing |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) | Sorted, random access |
| Hash lookup (set/dict) | O(1) | O(1) | O(n) | O(n) | Hashable keys |
For a single lookup on unsorted data, linear search wins. For repeated lookups, either sort once and use binary search (which also supports range and nearest-value queries) or build a hash set for pure membership tests. Related: Sorting and Data Structures.