Slide 7.8: Append.h
Slide 8.2: Evaluation of a binary search
Home

A Binary Search

On the average, a half of a file needs to be searched to locate the desired record by using a sequential search. The following slides will introduce a fast, simple searching algorithm: a binary search, which repeatedly divides an ordered search space in half according to how the required (key) value compares with the middle element.

The following pseudo-C routine performs a binary search which returns the index of the element of vector “thing[first..last]” equal to “target”:

Algorithm of a Binary Search 

 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 );

The interface below provides the three searches: sequential, binary, and Unix grep searching. They search for books in the URL by title matching.

  Enter a Title to Search for a Book in the URL.
   Title:
 

  URL:
 

Help
Search binary
Search sequentially
Search Unix
Show file content

  Password: