Nummber of Comparisons in Binary Search (worst Case)

Discussion in 'Homework Help' started by zulfi100, Jan 19, 2016.

Jun 7, 2012
320
0
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: Jan 19, 2016
2. WBahn Moderator

Mar 31, 2012
17,743
4,795
You aren't reading it closely enough.

Take another shot at it.

Jun 7, 2012
320
0
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.

Mar 31, 2012
17,743
4,795
Yes.