Nummber of Comparisons in Binary Search (worst Case)

Thread Starter

zulfi100

Joined Jun 7, 2012
630
Hi,
I have found answer for this on web as:

To analyze the binary search algorithm, we need to recall that each comparison eliminates about half of the remaining items from consideration. What is the maximum number of comparisons this algorithm will require to check the entire list? If we start with n items, then after first comparison , list is reduced to n/2 items, after second comparison to n/4 items, after 3rd to n/8 items, after 4th to n/16 items and after ith comparison the list would be reduced to n/(2 raised to the power i) items. The link http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html says that n/(raised to the power i) is 1. I cant understand this. Somebody please guide me.

Zulfi.
 
Last edited:

Thread Starter

zulfi100

Joined Jun 7, 2012
630
Hi,
I think i am able to understand it. If n=16,
then after 1st comparison, we would have n/2 items (=8)
after 2nd comparison, we would be left with n/4 items (=4)
after 3rd comparison, we would be left with n/8 items (=2)
& after 4th comparison, we would be left with n/16 items (=1 because n=16).

So the number of runs = 4.
which is same as log base 2 of(16)= 4.

Thanks.

Zulfi.
 
Top