Slide 13.9: FindBook.cpp

FindBook.cpp

This code is the implementation of the function Show data and index. It applies a binary search on the index (see left) to find the book record. Once the byte offset for the data record is found, a single seek is all that is required to retrieve the record. Again, the following pseudo-C routine (see right) performs a binary search which returns the index of the element of vector “thing[first..last]” equal to “target”.


10    17   
0201874016|0    
0471135852|436  
0471393073|210  
0521797561|512  
0596001436|174  
0596002920|122  
0672319462|293  
1565929470|76   
1591403456|353  
1930110081|549

 if ( target < thing[first] || target > thing[last] )
   return NOT_FOUND;
 while ( first < last )  {
   mid = ( first + last ) / 2;     /* truncate to integer */
   if ( target == thing[mid] )
     return  mid;
   if ( target < thing[mid] )
     last  = mid - 1;
   else
     first = mid + 1;
 }
 if ( target == thing[last] )
   return last;
 return  NOT_FOUND;

~wenchen/public_html/cgi-bin/351/week13/FindBook.cpp

#include  <fstream>
#include  <iostream>
#include  <cstring>
  using namespace  std;

#include  "Book_1.h"
#include  "Overload.h"

int  main( int argc, char* argv[ ] ) {
  fstream  index, file;
  Book     b;
  int      length, low, high, guess, result, count, offset;
  char     ISBN[11];

  index.open( "index.txt", fstream::in );
  index >> high >> length;
  low  = count = 1;

  while ( low <= high ) {
    guess = ( high + low ) / 2;
    index.seekg  ( 12+(guess-1)*length, fstream::beg );
    index.getline( ISBN, 11, '|' );
    index >> offset;
    cout << count++ << " comparisons; checking ISBN: " << ISBN << "<br>";
    if ( ( result = strcmp( argv[1], ISBN ) ) == 0 ) {
      file2.open ( "data.txt", fstream::in );
      file2.seekg( offset, fstream::beg );
      file2 >> b;
      b.PutResults( );
      file2.close( );
      break;
    }
    else if ( result < 0 )
      high = guess - 1;
    else
      low  = guess + 1;
  }

  if ( low > high ) {
    cout << "<br><br><h2>ISBN: " << argv[1]
         << " is not found.</h2>";
  }
  index.close( );
}