DSA 二分查找
二分查找
二分查找算法通过在一个数组中搜索并返回其查找值的索引。
速度
当前值: {{ currVal }}
{{ msgDone }}运行模拟，看看二分查找算法是如何工作的。
要查看当找不到某个值时会发生什么，请尝试查找值 5。
二分查找比线性查找快得多，但需要一个已排序的数组才能工作。
二分查找算法通过检查数组中间的值来工作。如果目标值较小，则下一个要检查的值位于数组左半部分的中心。这种搜索方式意味着搜索区域始终是前一个搜索区域的一半，这就是二分查找算法如此之快的原因。
这个将搜索区域减半的过程一直持续到找到目标值，或者直到数组的搜索区域为空。
工作原理
- 检查数组中的中间值。
- 如果目标值较小，则搜索数组的左半部分。如果目标值较大，则搜索右半部分。
- 继续执行步骤 1 和 2，对数组的新缩减部分进行搜索，直到找到目标值或搜索区域为空。
- 如果找到该值，则返回目标值的索引。如果未找到目标值，则返回 -1。
手动演练
让我们手动尝试一下搜索过程，以便在实际用编程语言实现之前，能更清楚地理解二分查找是如何工作的。我们将搜索值 11。
步骤 1: 我们从一个数组开始。
[ 2, 3, 7, 7, 11, 15, 25]
步骤 2: 数组中索引为 3 的中间值，它等于 11 吗？
[ 2, 3, 7, 7, 11, 15, 25]
步骤 3: 7 小于 11，所以我们必须在索引 3 的右侧搜索 11。索引 3 右侧的值为 [ 11, 15, 25]。下一个要检查的值是中间值 15，位于索引 5。
[ 2, 3, 7, 7, 11, 15, 25]
步骤 4: 15 大于 11，所以我们必须在索引 5 的左侧搜索。我们已经检查了索引 0-3，因此只有索引 4 还有值需要检查。
[ 2, 3, 7, 7, 11, 15, 25]
我们找到了！
在索引 4 处找到值 11。
返回索引位置 4。
二分查找完成。
运行下面的模拟，以动画形式查看以上步骤。
手动运行：发生了什么？
起初，算法有两个变量“left”和“right”。
“left”为 0，表示数组中第一个值的索引，“right”为 6，表示数组中最后一个值的索引。
\((left+right)/2=(0+6)/2=3\) 是用于检查中间值（7）是否等于目标值（11）的第一个索引。
7 小于目标值 11，因此在下一个循环中，搜索区域必须限制在中间值的右侧：[ 11, 15, 25]，位于索引 4-6。
为了限制搜索区域并找到一个新的中间值，“left”更新为索引 4，“right”仍然是 6。4 和 6 是新搜索区域的第一个和最后一个值的索引，即前一个中间值的右侧。新的中间值索引是 \((left+right)/2=(4+6)/2=10/2=5\)。
检查索引 5 处的新中间值：15 大于 11，所以如果目标值 11 存在于数组中，它必定在索引 5 的左侧。新搜索区域是通过将“right”从 6 更新为 4 来创建的。现在，“left”和“right”都是 4，\((left+right)/2=(4+4)/2=4\)，因此只剩下索引 4 需要检查。在索引 4 处找到目标值 11，因此返回索引 4。
总而言之，二分查找算法就是通过不断地将数组搜索区域减半，直到找到目标值。
当找到目标值时，将返回目标值的索引。如果未找到目标值，则返回 -1。
二分查找实现
要实现二分查找算法，我们需要
- 一个包含要搜索值的数组。
- 一个要搜索的目标值。
- 一个只要 left 索引小于或等于 right 索引就一直运行的循环。
- 一个 if 语句，用于比较中间值与目标值，并在找到目标值时返回索引。
- 一个 if 语句，用于检查目标值是否小于或大于中间值，并更新“left”或“right”变量以缩小搜索区域。
- 循环结束后，返回 -1，因为此时我们知道目标值未找到。
二分查找的结果代码如下：
示例
def binarySearch(arr, targetVal):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == targetVal:
return mid
if arr[mid] < targetVal:
left = mid + 1
else:
right = mid - 1
return -1
myArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
myTarget = 15
result = binarySearch(myArray, myTarget)
if result != -1:
print("Value",myTarget,"found at index", result)
else:
print("Target not found in array.")二分查找时间复杂度
有关时间复杂度的一般性解释，请访问此页面。
有关插入排序时间复杂度的更全面详细的解释，请访问此页面。
每次二分查找检查一个新值以确定它是否是目标值时，搜索区域都会减半。
这意味着，即使在最坏的情况下，二分查找也找不到目标值，它仍然只需要 \( \log_{2}n \) 次比较即可搜索完一个包含 \(n\) 个值的已排序数组。
二分查找的时间复杂度是
\[ O( \log_{2} n ) \]
注意: 在使用大 O 符号写时间复杂度时，我们也可以只写 \( O( \log n ) \)，但 \( O( \log_{2} n ) \) 提醒我们数组搜索区域每次新比较都会减半，这是二分查找的基本概念，所以在这里我们保留了以 2 为底的表示。
如果我们画出二分查找在包含 \(n\) 个值的数组中查找值所需的时间与线性查找的比较图，我们会得到这张图
运行下面的二分查找模拟，使用不同数量的值 \(n\) 的数组，并观察二分查找需要多少次比较才能找到目标值
{{ this.userX }}
操作次数：{{ operations }}
未找到！
正如你在运行二分查找模拟时所看到的，即使数组很大且我们正在寻找的值未找到，搜索也只需要很少的比较。
