Python 实现的二分查找
二分查找
二分查找算法在已排序数组中进行搜索，并返回其搜索值所在的索引。
{{ msgDone }}
运行模拟，查看二分查找算法的工作原理。
二分查找比线性查找快得多，但要求数组已排序才能工作。
二分查找算法通过检查数组中间位置的值来工作。如果目标值较低，则下一个要检查的值位于数组左半部分的中间位置。这种搜索方式意味着搜索区域始终是前一个搜索区域的一半，因此二分查找算法的速度非常快。
搜索区域减半的过程会一直持续，直到找到目标值，或者直到数组的搜索区域为空。
工作原理：
- 检查数组中间位置的值。
- 如果目标值较低，则搜索数组的左半部分。如果目标值较高，则搜索右半部分。
- 对数组新的缩小部分继续执行步骤 1 和 2，直到找到目标值或搜索区域为空。
- 如果找到该值，则返回目标值的索引。如果未找到目标值，则返回 -1。
手动运行示例
让我们尝试手动进行搜索，以便在实际在Python程序中实现二分查找之前，更好地了解其工作原理。我们将搜索值 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]。下一个要检查的值是索引 5 处的中间值 15。
[ 2, 3, 7, 7, 11, 15, 25]
第 4 步：15 高于 11，因此我们必须在索引 5 的左侧搜索。我们已经检查了索引 0-3，因此只剩下索引 4 需要检查。
[ 2, 3, 7, 7, 11, 15, 25]
我们找到了它！
值 11 位于索引 4。
返回索引位置 4。
二分查找结束。
运行下面的模拟，查看上述步骤的动画演示：
在 Python 中实现二分查找
要实现二分查找算法，我们需要：
- 包含待搜索值的数组。
- 要搜索的目标值。
- 循环，只要左索引小于或等于右索引就继续运行。
- if 语句，用于比较中间值与目标值，如果找到目标值则返回索引。
- if 语句，用于检查目标值是小于还是大于中间值，并更新“左”或“右”变量以缩小搜索区域。
- 循环结束后，返回 -1，因为此时我们知道未找到目标值。
二分查找的最终代码如下所示：
实例
在 Python 中创建二分查找算法：
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
mylist = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
x = 11
result = binarySearch(mylist, x)
if result != -1:
print("Found at index", result)
else:
print("Not found")
二分查找时间复杂度
每次二分查找检查一个新值以查看其是否为目标值时，搜索区域都会减半。
这意味着，即使在二分查找无法找到目标值的最坏情况下，它仍然只需要 \( \log_{2}n \) 次比较即可遍历包含 \(n\) 个值的已排序数组。
二分查找的时间复杂度为：\( O( \log_{2} n ) \)
注意：使用大 O 表示法表示时间复杂度时，我们也可以只写 \( O( \log n ) \)，但 \( O( \log_{2} n ) \) 提醒我们，每次新比较都会将数组搜索区域减半，这是二分查找的基本概念，因此在这种情况下，我们将保留以 2 为底数的表示法。
如果我们绘制二分查找在包含 \(n\) 个值的数组中查找某个值所需的时间图，并与线性查找进行比较，将得到下图：
