使用二分查找定位数组中所有 n 个排序的不同整数所需的比较总数是多少？我认为数字是 n log2 n(2 是基数)，但我不确定。你怎么认为？
最佳答案
如果你想要一个确切的答案，那么它显然不是 N log(N) 或 N log2(N)。对于大多数整数N，logN和log2都不是有理数，但比较次数必须是整数值。
此外，确切的答案将取决于二分搜索算法的实现细节。例如，如果“比较”是返回真和假的简单关系，则需要比“比较”返回负数、零或正数时更多的比较。 (在后一种情况下，您可以在算法提前击中关键时短路。)
关于java - 二分查找的比较次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2590479/