为什么二进制搜索 O(log n) 运行 4 次？

Question

我看了一些关于 O(log n) 时间复杂度的视频，但后来我尝试了网上教程中的几种二分查找法，我现在更糊涂了。

In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.

二分查找示例： https://jsfiddle.net/Hoyly/mhynk7gp/3/

function binarySearch(sortedArray, key){
    let start = 0;
    let end = sortedArray.length - 1;

    while (start <= end) {
        let middle = Math.floor((start + end) / 2);
                console.log('count',++count,sortedArray[middle]);
        if (sortedArray[middle] === key) {
            return middle;
        } else if (sortedArray[middle] < key) {
            start = middle + 1;
        } else {
            end = middle - 1;
        }
    }
    return -1;
}
let count= 0;
console.log('first 1:');
let res1 = binarySearch([1,2,3,4,5,6,7,8],8);
console.log('first 2:');
let res2 = binarySearch([1,2,3,4,5,6,7,8],1);
console.log('answer:',res1,res2);

正如您在 jsfiddle 中看到的那样

如果我试图在 8 长数组中找到“1”

方法调用次数为3
2^3 = 8
人们就是这样称呼它是一个 O(log n) 函数

但是如果我试图找到“8”

调用次数为4
2^4 != 8
绝对不是最坏情况下的 O(log n) 定义

Answer 1

时间复杂度是O(log n)，不是log n 没有大O的我就不解释全了这里 big-O 的意思；请参阅 definition on Wikipedia。

只要说它只给出运行时增长率的上限就够了n 增长，只有当 n 足够大时。即使 n = 8 导致 1000 次调用，算法仍然可能是 O(log n).

Answer 2

这里的二分查找可以多做一步，具体取决于你在数组的哪一半进行查找。如果它使用 Math.ceil 而不是 Math.floor，那么会找到 8分三步，而 1 分四步。

如果我们将其扩展到 128 个项目，那么最后一个项目将在 7 或 8 个步骤中找到（同样，取决于哪一半）。一般来说，所采取步骤的真正最坏情况是 log n + 1。但是，对于大O，我们不考虑常量，只考虑函数的增长率。 O(log n + 1) 简化为 O(log n)。同样的方式 O(2n) 仍然是 O(n).

为什么二进制搜索 O(log n) 运行 4 次？

Why is binary search O(log n), when it runs 4 times?

algorithm

search

binary-search

time-complexity

如果我试图在 8 长数组中找到“1”

但是如果我试图找到“8”