二分查找的时间复杂度
Time Complexity of Binary Search
我是编码新手，目前正在学习 searching/sorting 算法。目前，我正在研究二进制搜索，并且很难理解最坏情况下 O(log2 n) 的时间复杂度。有人可以向我清楚地解释如何进行以便我知道逻辑吗？ （一步一步）
这是伪代码：
binarySearch( list, value, low, high ){
if low <= high {
mid = (low + high)/ 2
if value == list[mid]
return mid
else if value < list[mid]
return binarySearch( list, value, low, mid - 1 )
else
return binarySearch( list, value, mid+1, high)
}
else
return -1
}
二分搜索通过将搜索区间重复分成两半来搜索排序数组。它以一个覆盖整个数组的区间开始。如果搜索关键字的值小于区间中间的项目，则将区间缩小到下半部分。否则，它将缩小到上半部分。它反复进行此检查，直到找到值（和 return 索引值）或间隔为空，然后 returns -1.
概述
暂时忘掉你的代码，看看纸上的算法，运行通过一些例子，看看一些可视化，直到你真正理解它。
看看这张我从Wikipedia偷来的插图：
每轮搜索范围有效减半。所以你在最近的 log_2(n) 步中找到了这个数字。
猜一个数字
您可能熟悉“猜数字游戏”。比赛进行得像
Think of a number between 0 and 100 but do not tell me the answer yet.
Now, I will try to guess the number and all you can say is:
- yes, correct answer
- no, the number is too high
- no, the number is too low
这个游戏的最优策略是，出其不意，二分查找。让我们快速玩一遍，您会更好地理解。
第一个猜测将是 50，因为它位于当前搜索范围 [0, 100] 的中间。我可能会说 50 现在太高了。这有效地将搜索范围减半到 [0, 49]，下一个猜测将是 25。
[0, 100], is it 50?
> too high
[0, 49], is it 25?
> too low
[26, 49], is it 38?
> too high
[26, 37], is it 32?
> too high
[26, 31], is it 28?
> too high
[26, 27], is it 27?
> too high
[26], is it 26?
> correct!
你刚刚见证了最坏的情况，所有的猜测都错了，直到只剩下26个。我们通过 7 个步骤找到了解决方案。 log_2(100) = 6.64...，所以这听起来是正确的。
那么为什么 log_2？
现在你应该明白了，搜索范围每一步都会减半。那么为什么这会导致 log_2 在数学上呢？
其实很简单。您多久可以将一个数字除以 2 直到小于等于 1？ log_2 次。换句话说，搜索范围何时从 n 个数字下降到 1 个数字 - 恰好 1 log_2(n) 个步骤。
1.从技术上讲，您必须将其四舍五入，因为没有 “步骤的分数”，所以 ceil(log_2(n))，但这并不重要。
请注意，由于 Big-O 在数学上的定义方式，O(log_2(n)) 和 O(log(n)) 表示同一组。所以你经常会看到 O(log(n))（没有 2）被指定为二进制搜索的时间复杂度。
代码
最后，让我们看一下您的伪代码，并说服自己它实际上与我们刚刚在“猜数字”游戏中使用的策略相同。
您的 list 和 low, high 指示搜索范围。作为第一步，您 select 中间的值：
mid = (low + high) / 2
在之前的游戏中，例如 [0, 100] 如何导致最初猜测 50，等等。
现在，您有了实际的猜测，查找：
if value == list[mid]
根据它是更高还是更低，您可以通过使用更小的搜索范围再次调用该方法来将搜索范围减半。即与
low, mid - 1，如果数字太高，- 或
mid + 1, high，如果数字太低。
在游戏中，根据 50 是太高还是太低，这是我们到达 [0, 49] 或 [51, 100] 的步骤。
我是编码新手，目前正在学习 searching/sorting 算法。目前，我正在研究二进制搜索，并且很难理解最坏情况下 O(log2 n) 的时间复杂度。有人可以向我清楚地解释如何进行以便我知道逻辑吗？ （一步一步）
这是伪代码：
binarySearch( list, value, low, high ){
if low <= high {
mid = (low + high)/ 2
if value == list[mid]
return mid
else if value < list[mid]
return binarySearch( list, value, low, mid - 1 )
else
return binarySearch( list, value, mid+1, high)
}
else
return -1
}
二分搜索通过将搜索区间重复分成两半来搜索排序数组。它以一个覆盖整个数组的区间开始。如果搜索关键字的值小于区间中间的项目，则将区间缩小到下半部分。否则，它将缩小到上半部分。它反复进行此检查，直到找到值（和 return 索引值）或间隔为空，然后 returns -1.
概述
暂时忘掉你的代码，看看纸上的算法，运行通过一些例子，看看一些可视化，直到你真正理解它。
看看这张我从Wikipedia偷来的插图：
每轮搜索范围有效减半。所以你在最近的 log_2(n) 步中找到了这个数字。
猜一个数字
您可能熟悉“猜数字游戏”。比赛进行得像
Think of a number between 0 and 100 but do not tell me the answer yet.
Now, I will try to guess the number and all you can say is:
- yes, correct answer
- no, the number is too high
- no, the number is too low
这个游戏的最优策略是，出其不意，二分查找。让我们快速玩一遍，您会更好地理解。
第一个猜测将是 50，因为它位于当前搜索范围 [0, 100] 的中间。我可能会说 50 现在太高了。这有效地将搜索范围减半到 [0, 49]，下一个猜测将是 25。
[0, 100], is it 50?
> too high
[0, 49], is it 25?
> too low
[26, 49], is it 38?
> too high
[26, 37], is it 32?
> too high
[26, 31], is it 28?
> too high
[26, 27], is it 27?
> too high
[26], is it 26?
> correct!
你刚刚见证了最坏的情况，所有的猜测都错了，直到只剩下26个。我们通过 7 个步骤找到了解决方案。 log_2(100) = 6.64...，所以这听起来是正确的。
那么为什么 log_2？
现在你应该明白了，搜索范围每一步都会减半。那么为什么这会导致 log_2 在数学上呢？
其实很简单。您多久可以将一个数字除以 2 直到小于等于 1？ log_2 次。换句话说，搜索范围何时从 n 个数字下降到 1 个数字 - 恰好 1 log_2(n) 个步骤。
1.从技术上讲，您必须将其四舍五入，因为没有 “步骤的分数”，所以 ceil(log_2(n))，但这并不重要。
请注意，由于 Big-O 在数学上的定义方式，O(log_2(n)) 和 O(log(n)) 表示同一组。所以你经常会看到 O(log(n))（没有 2）被指定为二进制搜索的时间复杂度。
代码
最后，让我们看一下您的伪代码，并说服自己它实际上与我们刚刚在“猜数字”游戏中使用的策略相同。
您的 list 和 low, high 指示搜索范围。作为第一步，您 select 中间的值：
mid = (low + high) / 2
在之前的游戏中，例如 [0, 100] 如何导致最初猜测 50，等等。
现在，您有了实际的猜测，查找：
if value == list[mid]
根据它是更高还是更低，您可以通过使用更小的搜索范围再次调用该方法来将搜索范围减半。即与
low, mid - 1，如果数字太高，- 或
mid + 1, high，如果数字太低。
在游戏中，根据 50 是太高还是太低，这是我们到达 [0, 49] 或 [51, 100] 的步骤。