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