Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!ihnp4!ptsfa!lll-lcc!styx!ames!rutgers!princeton!allegra!alice!ark
From: ark@alice.UUCP
Newsgroups: comp.sources.d
Subject: Re: "look" utility?
Message-ID: <6672@alice.uUCp>
Date: Fri, 27-Feb-87 17:22:01 EST
Article-I.D.: alice.6672
Posted: Fri Feb 27 17:22:01 1987
Date-Received: Sun, 1-Mar-87 15:06:33 EST
References: <1916@cbdkc1.UUCP> <837@maynard.BSW.COM> <1145@ihlpf.ATT.COM>
Organization: AT&T Bell Laboratories, Liberty Corner NJ
Lines: 23

In article <1145@ihlpf.ATT.COM>, straka@ihlpf.UUCP writes:
> >     look consults a sorted file and prints all lines that begin with string.
> >     It uses binary search.
> > Note that look searches for a literal string, not a regular expression.
> > You could use grep, but for a sizable file look can be hundreds of times
> > faster.
> 
> 
> What about using fgrep?
> Or possibly grep "^string"?

The run time of any program of the grep family increases linearly
with the size of the file being searched (with some exceptions for
complicated patterns in grep).

Look, on the other hand, doesn't touch the entire file.  That is,
after all, the essence of binary search.  So the run time increases
only logarithmically with the size of the file.

That difference is nothing to sneeze at.  Consider a file with a
million records as an example: a program that can find any record
with only 20 probes into the file is going to beat almost any linear
search you can imagine.