Lightweight Databases

Binary Search

This function gets a filehandle open to a sorted file
It finds the first line in the file that is ge $key
Returns that line and leaves $fh positioned at that line

        sub search {
          my ($fh, $key) = @_;

          my ($lo, $hi) = (0, -s $fh);

          while (1) {
            my $mid = int(($lo + $hi)/2);

            if ($mid) {
              seek $fh, $mid-1, SEEK_SET;
              my $junk = <$fh>;
            } else { 
              seek $fh, 0, SEEK_SET; 
            }

            my $start = tell $fh;
            my $rec = <$fh>;
            return unless defined $rec; 
            chomp $rec;

            if ($hi == $lo) {
              seek $fh, $start, SEEK_SET;
              return $rec 
            }

            if ($rec lt $key) { $lo = $mid+1 }
            else              { $hi = $mid   }
          }
        }

This is search1.pl in your handout