Analysis of binary search

  1. read n, the number of entries in the phone book
  2. read N1 ,..., Nn, T1 ,..., Tn
  3. read NAME
  4. beginning <- 1
  5. end <- n
  6. found <- false
  7. repeat until either found or beginning > end
  8.   middle <- (beginning + end)/2
  9.   if NAME = Nmiddle then
  10.     write Tmiddle
  11.     found <- true
  12.   else
  13.     if NAME < Nmiddle then
  14.       end <- middle - 1
  15.     else
  16.       beginning <- middle + 1 // end until
  17. if not found then
  18.   write "Sorry, but the name is not in the directory."
  19. Stop
We only analyze the search (Steps 4-19 ), as we assume that the phone book is always available.

Each execution of the repeat loop requires a constant amount of time, so we really only need to count the number of executions of the loop.

Since (end -beginning) is halved each time through the loop, the loop is executed at most:

[ log2n] = [lg n] times.

 

Hence the worst-case time complexity of binary search is

O(lg n)

This is far superior to the O(n) time complexity of sequential search.

 

 

[Prev][TOC][Next]


CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000