Searching¶
Searching returns a matching value, its location, or a boundary at which it could be inserted. The input's structure determines what is possible.
| Algorithm | Required input | Worst-case time | Auxiliary space |
|---|---|---|---|
| Linear search | Any finite sequence | Θ(n) |
Θ(1) |
| Binary search | Random-access sorted sequence | Θ(log n) |
Θ(1) iterative |
| Hash lookup | Hash table and suitable hashing | Θ(n), expected O(1) |
Structure-dependent |
| Balanced-tree lookup | Ordered balanced search tree | Θ(log n) |
Structure-dependent |
Sorting solely to perform one binary search normally costs more than scanning once. Sorting can be worthwhile when many subsequent queries reuse the same ordered data.