number of comparisons of binary search

Question

What is the total number of comparisons necessary to locate all the n sorted distinct integers in an array using binary search? I think the number is n log₂ n (2 is the base), but I am not sure. What do you think?

Answer 1

If you want an exact answer, then it is clearly not N log(N) or N log₂(N). For most integers N, logN and log₂ are not rational, but the number of comparisons must be an integer value.

Also, the exact answer will depend on implementation details of the binary search algorithm. For example, if a "comparison" is a simple relation that returns true and false, more comparisons are required than when a "comparison" returns negative, zero or positive. (In the latter case, you can short circuit when the algorithm hits the key early.)