Question :

Suppose we carry out a binary search of an ordered list of 63 items: We are searching for an item X which occurs exactly once in the list.

How many comparisons are carried out

i. in the worst case scenario

ii. in the best case scenario

iii. on average (here your answer need not be an integer)

Following the previous example, suppose in the ordered list of 63 items, X occurs three times.

Calculate how many comparisons, on average, are necessary, using binary search, to find one of the X's.