
We only analyze the search (Steps 419 ), 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: [ log_{2}n] = [lg n] times.

Hence the worstcase time complexity of binary search is
This is far superior to the O(n) time complexity of sequential
search.
CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000