DSA 选择排序时间复杂度
请查看此页面了解时间复杂度的一般解释。
二分搜索时间复杂度
二分搜索 通过检查中间值在已排序的数组中查找目标值。如果中间值不是目标值，则线性搜索选择左子数组或右子数组并继续搜索，直到找到目标值。
要找到二分搜索的时间复杂度，让我们看看在一个包含 \(n\) 个值的数组中查找目标值需要多少次比较操作。
最佳情况是第一个中间值与目标值相同。如果发生这种情况，目标值将立即找到，并且只进行一次比较，因此在这种情况下时间复杂度为 \(O(1)\)。
最坏情况是搜索区域必须反复减半，直到搜索区域只有一个值。当这种情况发生时，无论是否找到目标值，它都不会影响时间复杂度。
让我们考虑数组长度为 2 的幂，例如 2、4、8、16、32 64 等。
将 2 减半多少次才能看到只有一个值？只有一次，对吧？
8 怎么样？我们必须将 8 个值的数组减半 3 次才能得到一个值。
32 个值的数组必须减半 5 次。
我们可以看到 \(2=2^1\)，\(8=2^3\) 和 \(32=2^5\)。因此，将数组分割成只有一个元素所需减半的次数可以在以 2 为底的幂中找到。换句话说，我们可以问“我必须将 2 自身相乘多少次才能得到这个数字？”。从数学上来说，我们可以使用以 2 为底的对数，因此我们可以发现长度为 \(n\) 的数组可以被分割成 \( \log_{2}(n)\) 次。
这意味着二分搜索的时间复杂度是
\[ \underline{\underline{O( \log_{2} n )}} \]
平均情况并不那么容易确定，但由于我们理解算法的时间复杂度是使用大 O 符号表示的最坏情况的上界，因此平均情况并不那么有趣。
注意：二分搜索的时间复杂度 \(O( \log_{2}n)\) 比线性搜索 \(O(n)\) 快得多，但重要的是要记住二分搜索需要一个排序数组，而线性搜索不需要。
如果我们绘制二分搜索在一个包含 \(n\) 个值的数组中查找值所需的时间与线性搜索相比，我们会得到以下图形
二分搜索模拟
运行数组中不同值 \(n\) 的模拟，并查看二分搜索查找目标值所需多少次比较。
{{ this.userX }}
操作：{{ operations }}
未找到！
正如你在运行二分搜索模拟时所看到的，即使数组很大，我们正在寻找的值没有找到，搜索也只需要很少的比较次数。
