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