Searching (cont)
Since searching is a very important/frequent operation,
many approaches have been developed to do it
- Linear structures: arrays, linked lists
- Arrays = random access. Lists = sequential access
Cost of searching:
| Array | List |
| Unsorted | O(n)
(linear scan) |
O(n)
(linear scan) |
| Sorted | O(log n)
(binary search) |
O(n)
(linear scan) |
- O(n) … linear scan (search technique of last resort)
- O(log n) … binary search, search trees (trees also have other uses)
Also (cf. Sedgewick Ch.14): hash tables (O(1), but only under optimal conditions)
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}