# Implements a binary search on a sorted word list
# (in a text file).  Very similar to Search::Dict (a standard
# module) so use it instead where appropriate.  Intended as an
# example of binary-searching a file.
#
# search("word") returns the byte offset if lowercase "word"
#     is found in *W
#     or undef if it's not found.
#
# (Assumes filehandle W is open to the dictionary file.)
sub search {
        my($word, $start, $end)=@_;
        my($guess, $offset, $preguess);
        no warnings 'uninitialized';

        $end=-s W unless defined $end;
        $offset=int(($end-$start)/2+$start);
        seek(W, $offset, 0);   # Go there.
        while($offset and getc(W) ne "\n") {
                seek(W, --$offset, 0);
        }
        $preguess=tell(W);
        $guess=<W>;
        chomp($guess);
        $guess=lc($guess);
        return $preguess if $guess eq $word;

        if ($word gt $guess) {
                return if ($offset==$_[1] and $end==$_[2]);
                { local $_=tell(W);
                   if (<W> eq lc("$word\n")) { # Try the next word too
+.
                        return $_;
                   } }
                @_=($word, $preguess, $end);
        } else {
                return if ($start==$_[1] and $offset==$_[2]);
                @_=($word, $start, $preguess);
        }
        goto &search;
}
[download]