DSA 二分查找
二分查找
二分查找算法搜索数组并返回搜索值的索引。
速度
当前值: {{ currVal }}
{{ msgDone }}运行模拟以查看二分查找算法的工作原理。
要查看未找到值时会发生什么，请尝试查找值 5。
二分查找比线性查找快得多，但需要排序后的数组才能工作。
二分查找算法通过检查数组中心的 value 来工作。如果目标值较低，则要检查的下一个值位于数组左半部分的中心。这种搜索方式意味着搜索区域始终是先前搜索区域的一半，这就是二分查找算法如此快的原因。
这种将搜索区域减半的过程会一直持续到找到目标值，或者直到搜索区域为空。
工作原理
- 检查数组中心的 value。
- 如果目标值较低，则搜索数组的左半部分。如果目标值较高，则搜索右半部分。
- 继续步骤 1 和 2，针对新减少的数组部分，直到找到目标值或直到搜索区域为空。
- 如果找到值，则返回目标值的索引。如果未找到目标值，则返回 -1。
手动运行
让我们尝试手动进行搜索，以便在实际使用编程语言实现它之前，更好地理解二分查找的工作原理。我们将搜索值 11。
**步骤 1：** 我们从一个数组开始。
[ 2, 3, 7, 7, 11, 15, 25]
**步骤 2：** 数组中间的 value，索引为 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。
二分查找实现
为了实现二分查找算法，我们需要
- 一个包含要搜索值的数组。
- 要搜索的目标值。
- 一个循环，只要左索引小于或等于右索引就运行。
- 一个 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 }}
未找到！
正如您在运行二分查找模拟时所看到的，即使数组很大且我们正在查找的值未找到，搜索也只需要很少的比较次数。
