二进制搜索（1 + log（n））中的最大键如何比较而不是log（n）？
How is maximum key compare in binary search (1+log(n)) not log(n)?
我正在阅读关于 BS 的更通用的解释。其中有一个介词，即二进制搜索中的最大键比较数是 (1+log(n))。我试图形成一种直觉，这怎么可能。我知道 BS 的破坏时间是 (log(n))。此外，我推测当我们搜索数组中不存在的元素时，会发生更糟糕的 time/maximum 键查找。但是每次我检查一个假设的数组做一个 BS 我最终得到 (log(n)) compares/steps 永远不会超过那个。这是用于构成该介词的代码。
public static int binarySearch(int[] a, int key){
int lo = 0, hi = a.length-1;
while (lo <= hi){
int mid = lo + (hi - lo) / 2;
if (key < a[mid])
hi = mid - 1;
else if (key > a[mid])
lo = mid + 1;
else
return mid;
}
return -1;
}
可能我的猜测是错误的，或者我遗漏了一些要点。如果您能解释最大可能的键比较是 (1+log(n))，那将非常感谢。
不要忘记，即使你只有1个元素，你仍然要猜测它，因为目标可能不在数组中。因此，当我们只剩下最后一个元素时，我们需要为最后的猜测添加 +1。
n=1想一想可能就更清楚了。我们还需要 1 次猜测，但是 log_2(1) = 0。所以我们需要加一个+1来修正公式。
当n不是2的次方时，直接上2的次方。对于长度为1000的数组，2的次方为1024，即10. 因此，对于 1000 个元素的数组，二分查找最多需要 11 (10 + 1) 次猜测。
Why?
在最坏的情况下，二分查找需要 10 个步骤来分离剩余的数字，最后需要 1 个步骤来检查是否只剩下一个数字是你想要的，或者它不在数组中。
想象一个大小为 8 的数组。
l=0, h = 7, mid = 0 + (7-0)/2 = 3 go right
l=4, h = 7, mid = 4 + (7-4)/2 = 5 go right
l=6, h = 7, mid = 6 + (7-6)/2 = 6 go right
l=7, h = 7, mid = 7 + (7-7)/2 = 7 go left
l=7, h=6 ====> terminates
Total comparisons = 1 + Log 8 = 4
EDIT1：想象这个数组并使用笔和纸描绘出上述步骤。搜索值 13。
index: 0 1 2 3 4 5 6 7
------------------------------
element: 1 3 5 6 7 9 11 15
这是思考您正在做的事情的另一种方式。不要将二分搜索视为搜索数组的元素，而是将二分搜索视为搜索 数组中元素之间的分隔符 。具体来说，想象一下这样对数组进行编号：
+-----+-----+-----+-----+-----+
| 0 | 1 | 2 | ... | n-1 |
+-----+-----+-----+-----+-----+
现在，给分隔符编号：
+-----+-----+-----+-----+-----+
| 0 | 1 | 2 | ... | n-1 |
+-----+-----+-----+-----+-----+
0 1 2 3 .. n-1 n
请注意，共有 n+1 个分隔符，一个在每个元素之前，一个在最后一个元素之后。
无论何时进行二分查找，您都在探查中间 分隔符 的索引（您知道为什么吗？）并丢弃了一半的分隔符。你可以 only throw half of a collection of k items away log2 k times 在你只剩下一个元素之前。这意味着需要的探测数将是⌈log2 (n+1)⌉，而恰好是
log2 n < ⌈log2 (n+1)⌉ ≤ log2 n + 1,
所以“1 + log n”位最终更多地来自 "throw away half the separators" 而不是来自其他来源。
希望对您有所帮助！
我正在阅读关于 BS 的更通用的解释。其中有一个介词，即二进制搜索中的最大键比较数是 (1+log(n))。我试图形成一种直觉，这怎么可能。我知道 BS 的破坏时间是 (log(n))。此外，我推测当我们搜索数组中不存在的元素时，会发生更糟糕的 time/maximum 键查找。但是每次我检查一个假设的数组做一个 BS 我最终得到 (log(n)) compares/steps 永远不会超过那个。这是用于构成该介词的代码。
public static int binarySearch(int[] a, int key){
int lo = 0, hi = a.length-1;
while (lo <= hi){
int mid = lo + (hi - lo) / 2;
if (key < a[mid])
hi = mid - 1;
else if (key > a[mid])
lo = mid + 1;
else
return mid;
}
return -1;
}
可能我的猜测是错误的，或者我遗漏了一些要点。如果您能解释最大可能的键比较是 (1+log(n))，那将非常感谢。
不要忘记，即使你只有1个元素，你仍然要猜测它，因为目标可能不在数组中。因此，当我们只剩下最后一个元素时，我们需要为最后的猜测添加 +1。
n=1想一想可能就更清楚了。我们还需要 1 次猜测，但是 log_2(1) = 0。所以我们需要加一个+1来修正公式。
当n不是2的次方时，直接上2的次方。对于长度为1000的数组，2的次方为1024，即10. 因此，对于 1000 个元素的数组，二分查找最多需要 11 (10 + 1) 次猜测。
Why?
在最坏的情况下，二分查找需要 10 个步骤来分离剩余的数字，最后需要 1 个步骤来检查是否只剩下一个数字是你想要的，或者它不在数组中。
想象一个大小为 8 的数组。
l=0, h = 7, mid = 0 + (7-0)/2 = 3 go right
l=4, h = 7, mid = 4 + (7-4)/2 = 5 go right
l=6, h = 7, mid = 6 + (7-6)/2 = 6 go right
l=7, h = 7, mid = 7 + (7-7)/2 = 7 go left
l=7, h=6 ====> terminates
Total comparisons = 1 + Log 8 = 4
EDIT1：想象这个数组并使用笔和纸描绘出上述步骤。搜索值 13。
index: 0 1 2 3 4 5 6 7
------------------------------
element: 1 3 5 6 7 9 11 15
这是思考您正在做的事情的另一种方式。不要将二分搜索视为搜索数组的元素，而是将二分搜索视为搜索 数组中元素之间的分隔符 。具体来说，想象一下这样对数组进行编号：
+-----+-----+-----+-----+-----+
| 0 | 1 | 2 | ... | n-1 |
+-----+-----+-----+-----+-----+
现在，给分隔符编号：
+-----+-----+-----+-----+-----+
| 0 | 1 | 2 | ... | n-1 |
+-----+-----+-----+-----+-----+
0 1 2 3 .. n-1 n
请注意，共有 n+1 个分隔符，一个在每个元素之前，一个在最后一个元素之后。
无论何时进行二分查找，您都在探查中间 分隔符 的索引（您知道为什么吗？）并丢弃了一半的分隔符。你可以 only throw half of a collection of k items away log2 k times 在你只剩下一个元素之前。这意味着需要的探测数将是⌈log2 (n+1)⌉，而恰好是
log2 n < ⌈log2 (n+1)⌉ ≤ log2 n + 1,
所以“1 + log n”位最终更多地来自 "throw away half the separators" 而不是来自其他来源。
希望对您有所帮助！