Searching in Linear Structures
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(logn)
(binary search) |
O(n)
(linear scan) |
O(logn)
(seek,seek,...) |
Although fseek() gives expensive random-access
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}