使用二进制搜索在数组中定位所有 n 个已排序的不同整数所需的比较总数是多少？我认为数字是n log 2 n（2 是底数），但我不确定。你怎么看？
问问题
6960 次
5 回答
3
如果你想要一个准确的答案，那么显然不是N log(N) 或 N log 2 (N)。对于大多数整数 N，logN 和 log 2不是有理数，但比较次数必须是整数值。
此外，确切的答案将取决于二进制搜索算法的实现细节。例如，如果“比较”是返回真假的简单关系，则比“比较”返回负数、零或正数时需要更多的比较。（在后一种情况下，您可以在算法提前击键时短路。）
于 2010-04-07T06:43:22.233 回答
1
找到每一个都需要log2 n，而且需要n多次完成，n log n事实就是如此。
于 2010-04-07T06:43:35.200 回答
0
我会说需要n log m
其中m是数组的大小，所以log m要找一个值。然后你n对n不同的整数执行此操作。
所以n log m总的来说。
于 2010-04-07T07:29:32.573 回答
0
对于 1 个数字，最多会有 (2 * log 2 n + 1) 向下舍入（所以 7.6 => 7）比较。
当我们在数组中找到某个数字时，首先我们检查它是否是我们正在寻找的那个。（== 第一次比较）。之后我们检查它是否更小（或更大）（第二次比较）。
要找到这个数字，我们最多必须处理 log 2 n 个数字。
我们必须对最后一个数字进行最后一次比较，以检查这是不是那个。
因此，在 [1..16] 中查找 16 需要 2*log 2 16 + 1 = 9 次比较（假设我们使用这些数字：8、12、14、15、16）。在 [1..10] 中寻找 10 将需要 2*log 2 10 + 1 = 7.6 => 7（假设我们落在这些数字上：5、8、9、10）。
因此，对于 n 个数字，最多会有 n 倍。
于 2010-04-07T08:33:41.373 回答
0
谢谢你的评论，现在我清楚了。我认为斯蒂芬 C 说的是真的。我认为除非我们有一个确切的值，否则我们实际上无法为这个问题制定一个公式。但是，如果 n=2^n -1，如 511(2^9 -1)，则很容易计算。对于 511，比较总数 = 1x1 + 2X2 + 3X4 + 4X8 + 5X16 + 6X32 + 7X64 + 8X128 + 9X256 = 4097。
于 2010-04-07T17:26:09.250 回答