Slide 8.2: Evaluation of a binary search

Evaluation of a Binary Search

The sequential and binary searching work on fixed-length records. Below is an example of input files:

10    85   
Advances in Security and Payment Methods for Mobile Commerce|1591403456|89.95|182|  
Dynamic WAP Application Development|1930110081|34.59|18|                            
File Structures: An Object-Oriented Approach with C++|0201874016|94.80|360|         
Java and XSLT|0596001436|26.37|890|                                                 
Learning WML & WMLScript|1565929470|17.48|12|                                       
M Commerce: Technologies, Services, and Business Models|0471135852|23.09|5|         
Mobile Commerce|0521797561|29.51|93|                                                
WAP Development with WML and WMLScript|0672319462|18.99|56|                         
WAP Servlets: Developing Dynamic Web Content With Java and WML|047139307|32.99|4|   
XML in a Nutshell, 2nd Edition|0596002920|39.95|39|

It is structured as follows:

The first record is number+' '+length+'\n' where the number is the number of records and the length is the record length. Each of number and length is 5 bytes.
For the remaining records, each record is with length bytes. If a record length is less than length, pad spaces at the end of the record until its length reaches to length.

Assume a file with n records, the following table gives comparisons between these two searches. The numbers in parentheses are the numbers of comparisons when the n is equal to 1000 or 2000 records.

	A Sequential Search	A Binary Search
On average	n/2 comparisons (500 or 1000)	⌊log₂ n⌋ + ½ comparisons (9½ or 10½)
At most	n comparisons (1000 or 2000)	⌊log₂ n⌋ + 1 comparisons (10 or 11)
Order	O(n)	O(log₂ n)

Binary searching is clearly a more attractive way to find things than sequential searching, but it works only when the list of records is ordered in terms of the key such as book title we are using in the search.