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

Question

我看过一些关于O(log n)时间复杂度的视频， 但后来我在互联网教程上尝试了几种二进制搜索方法， 我现在更困惑了。

在计算机科学中，大 O 表示法用于根据算法的运行时间或空间需求如何随着输入大小的增长而增长来对算法进行分类。

一个示例二叉搜索： 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">

1. 方法调用计数为3
2. 2^3 = 8
3. 这就是人们如何称呼它是一个 O(log n) 函数

但是如果我尝试找到"8">

1. 调用计数为4
2. 2^4 ！= 8
3. 从最坏的情况来看，这绝对不是O(log n)定义

Answer 1

时间复杂度是O(log n)，而不是没有大O的logn。我不会在这里解释 big-O 的全部含义;请参阅维基百科上的定义。

可以说，它只给出了运行时随着 n 的增长而增长的上限，并且只有当 n足够大时。即使 n= 8 导致 1000 次调用，算法仍可以是 O(logn)。

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).