What'll happen if log2(len(list)) is not an integer while doing binary search? How many operati-CodePudding

I'm trying to figure out how many operations binary search would have to do if it were given an array whose's length when "logged" with base 2 would not result in a whole number.

I don't really know what to do.

CodePudding user response：

Ceiled to the immediate superior integer. You can't do "0.2" operations, it's one or zero, and you need to do "something more"... So a whole operation.

For an array of 5 elements, your binary search is (worst case):

(O = non tested, - = rejected, X = value to search)

X O O O O
    ^ Start here.   Op. #1
X O - - -
  ^ New pivot       Op. #2
X - - - -
^ Found             Op. #3

As you see, you get exactly the same number of operations that a worst case for 8 elements, the next power of two. And log2(5)=2.32..., ceiled to 3, and that's what the worst case shown too.

CodePudding user response：

There's three cases in binary search: the pivot matches, it's too large, or it's too small. If your list is length n, and the pivot is at index floor(n/2), the new problem has size 0, floor((n-1)/2), ceil((n-1)/2).

The worst-case is when you choose the ceil((n-1)/2) case each time. This gives the recurrence relation for the worst-case number of comparisons for a list of size n as:

C(0) = 0
C(n) = 1   C(ceil((n-1)/2)) = 1   C(floor(n/2))

A moment's thought shows that C(n) is the length of n in binary digits, which for n>0 is floor(log_2(n)) 1.