Nummber of Comparisons in Binary Search (worst Case)

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

  1. zulfi100

    Thread Starter Member

    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.
     
  3. zulfi100

    Thread Starter Member

    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.
     
  4. WBahn

    Moderator

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