Number of binary search comparisons

Question

What is the total number of comparisons needed to find all n sorted individual integers in an array using binary search? I think the number n is log ₂ n (2 is the base), but I'm not sure. What do you think?

Answer 1

If you need 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 should be an integer value.

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

Answer 2

To search for each of them is required log2 n, and this needs to be done nonce, therefore n log nit is.

Answer 3

, n log m

m - , log m, . n n .

n log m .

Answer 4

(2 * log ₂ n + 1) ( 7.6 = > 7) 1 .

, , , . (== ). , ( ) ( ).

, log ₂ n .

, , .

, 16 [1..16] 2 * log ₂ 16 + 1 = 9 ( , : 8, 12, 14, 15, 16). 10 [1..10] 2 * log ₂ 10 + 1 = 7.6 = > 7 (, : 5, 8, 9, 10).

So, for n numbers, it will be at most n times larger.

Answer 5

Thanks for your comments, now I understand. I think Stephen C told the truth. I think that we cannot actually develop a formula for this question if we do not have an exact value. However, if n = 2 ^ n-1, like 511 (2 ^ 9 -1), it is easy to calculate. For 511, the total number of comparisons = 1x1 + 2X2 + 3X4 + 4X8 + ​​5X16 + 6X32 + 7X64 + 8X128 + 9X256 = 4097.