4 ms·
You don't need to know the number of the line you're looking at. You jump to the middle of the file, and you compare the nearest line to the search pattern. The
by mtdewcmu 11y ago
You don't need to know the number of the line you're looking at. You jump to the middle of the file, and you compare the nearest line to the search pattern. Then you recurse on the top or bottom half.
- userbinator 11y agoThat still requires random seeking; it's not so bad on SSDs, but abysmal on rotating disks, and most of the filesystem and OS caching code is optimised for linear forward reads, so things like prefetching are not going to help at all.
- mtdewcmu 11y agoAt some point the cost of scanning a long file will overcome the cost of doing log(n) seeks. On short files, it really doesn't matter what you do, searching will be fast regardless.