二分查找的比较次数
使用二分查找查找数组中所有 n 个已排序的不同整数所需的比较总数是多少？我认为这个数字是n log2 n（2是基数），但我不确定。你怎么认为？
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 log2 n (2 is the base), but I am not sure. What do you think?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
如果你想要一个准确的答案，那么显然不是 N log(N) 或 N log2(N)。对于大多数整数 N，logN 和 log2 不是有理数，但比较次数必须是整数值。
此外，确切的答案将取决于二分搜索算法的实现细节。例如，如果“比较”是返回 true 和 false 的简单关系，则比“比较”返回负数、零或正数时需要更多的比较。 （在后一种情况下，当算法提前命中关键时，您可以短路。）
If you want an exact answer, then it is clearly not N log(N) or N log2(N). For most integers N, logN and log2 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.)
找到每一个都需要
log2 n，并且需要完成n次，所以是n log n。It takes
log2 nto find each one, and it needs to be donentimes, son log nit is.我想说需要
n log m其中 m 是数组的大小，因此
log m才能找到一个值。然后对
n个不同的整数执行此n次。所以总共是
n log m。I would say it takes
n log mWhere m is the size of the array, so
log mto find a value.And then you do this
ntimes for thendistinct integers.So
n log min total.对于 1 个数字，最多会进行 (2 * log2n + 1) 次四舍五入（因此 7.6 => 7）次比较。
当我们找到数组中的某个数字时，首先我们检查它是否是我们要查找的数字。
（==第一次比较）。
之后我们检查它是否更小（或更大）（第二次比较）。
为了找到这个数字，我们必须处理最多 log2n 个数字。
我们必须对最后一个数字进行最后一次比较，以检查这是否是那个数字。
因此，在 [1..16] 中查找 16 将需要 2*log216 + 1 = 9 次比较（假设我们找到这些数字：8、12、14、15、16）。在 [1..10] 中查找 10 将需要 2*log210 + 1 = 7.6 => 7（假设我们得到这些数字：5、8、9、10）。
因此，对于 n 个数字，最多最多有 n 倍。
There will be at most (2 * log2n + 1) rounded down(so 7.6 => 7) comparisons for 1 number.
When we land on some number in array, first we check if it is the one we are looking for.
(== first comparison).
After that we check if it smaller (or greater) (second comparison).
To find the number, we must process at most log2n numbers.
And we must make the last comparison on the last number, to check that this is the one.
So looking for 16 in [1..16] will take 2*log216 + 1 = 9 comparisons (assuming we land on these numbers: 8, 12, 14, 15, 16). And looking for 10 in [1..10] will take 2*log210 + 1 = 7.6 => 7 (Assuming we land on these numbers: 5, 8, 9, 10).
So for n numbers there will be at most n times more.
谢谢你的评论，现在我清楚了。我认为Stephen C说的是真的。我认为除非我们有一个确切的值，否则我们实际上无法得出这个问题的公式。然而，如果n=2^n -1，如511(2^9 -1)，则很容易计算。对于 511，比较总数 = 1x1 + 2X2 + 3X4 + 4X8 + 5X16 + 6X32 + 7X64 + 8X128 + 9X256 = 4097。
Thanks for your comments, now I am clear. I think what Stephen C said is true. I think we cannot actually work out a formula for this question unless we have a exact value. However, if the n=2^n -1,like 511(2^9 -1), it is easy to compute. For 511, total number of comparisons = 1x1 + 2X2 + 3X4 + 4X8 + 5X16 + 6X32 + 7X64 + 8X128 + 9X256 = 4097.