As long as I have been using *nixes, I have never met a machine that didn't have grep. It was written by Ken Thompson himself in 1974, or 41 years ago, and first came out in Unix 4th edition.

grep is also specified by POSIX, whereas look isn't.

The interesting thing about look is that it uses binary search, so it is much faster.

Binary search is useless unless the file is sorted. Most often my files are not sorted, so egrep '^line' works just fine.

It obvious that look was written as an optimization for this specific case though. The default file is the user dictionary which is interesting. Do you think they didn't know about grep in 1979?

The interesting use case for me is that you can make a sorted index and look up records efficiently, i.e. within a script. It works with ctags indexes, for instance.

Binary search is only faster if access to the elements is constant-time, which is not true for a file with varying-length records (lines). Line 1000 (counting from 0) could be at offset 2000 if each line is a single character + newline, or it could be at offset 2000000 if each line is 999 characters and a newline, or somewhere in between.

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.

That 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.

At 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.

It's probably much faster in most cases of text files though.

I also think your constant time claim sounds too strong. You can eat a lot of end of line search time after the binary search and still beat a linear/regex search.

As someone else pointed out, look can also exit sooner.

According to Wikipedia, grep was first used in "Version 4 AT&T UNIX" According to my 1984 Eunice manual, Look was part of the 7th edition of Unix.