Search code examples
algorithmsearchbinary-searchlogarithm

What'll happen if log2(len(list)) is not an integer while doing binary search? How many operations will it have to do?

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.

Solution

  • 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.