Path: utzoo!attcan!uunet!tektronix!orca!tekecs!frip!andrew
From: andrew@frip.gwd.tek.com (Andrew Klossner)
Newsgroups: comp.unix.wizards
Subject: grep "sorted file" inappropriate (was Re: new grep)
Message-ID: <10132@tekecs.TEK.COM>
Date: 2 Jul 88 07:29:39 GMT
References: <16237@brl-adm.ARPA> <4219@mtgzz.att.com> <199@elgar.UUCP> <2561@homxc.UUCP>
Sender: andrew@tekecs.TEK.COM
Organization: Tektronix, Wilsonville, Oregon
Lines: 22

[]

	"How about an option (only applicable when patterns start with
	"^") to tell grep that the file is lexically sorted (?what
	order?) so it can terminate if the input line is lexically
	greater than the pattern (s).  This is useful for searching
	through sorted lists (files, dictionaries, etc...)"

If your pattern is a string (no meta-characters), what you really want
is a binary search, as implemented by the Berkeley look(1) command.
This is a different sort of operation than grep's sequential search,
and offering it as a separate command makes sense.

If your pattern contains meta-characters, its position in a sorted list
isn't necessarily defined.  For example, when do you stop searching
when the pattern is "^.rwx"?  You could define rules that specify when
to stop searching for each of several different forms of pattern, based
on the existing pattern algebra, but this starts to be more complexity
than the problem merits.

  -=- Andrew Klossner   (decvax!tektronix!tekecs!andrew)       [UUCP]
                        (andrew%tekecs.tek.com@relay.cs.net)   [ARPA]