Analysis of binary search

 read n, the number of entries in the phone book read N1 ,..., Nn, T1 ,..., Tn read NAME beginning <- 1 end <- n found <- false repeat until either found or beginning > end   middle <- (beginning + end)/2   if NAME = Nmiddle then     write Tmiddle     found <- true   else     if NAME < Nmiddle then       end <- middle - 1     else       beginning <- middle + 1 // end until if not found then   write "Sorry, but the name is not in the directory." 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.

CS1104 Main Page
Last Updated 01/05/2000