介绍
二分查找算法是一种在有序数据集中定位特定对象的高效搜索技术。该算法首先确定数据集的中间值。它将目标值与该中间值进行比较，并可以采取以下三种可能的操作之一：
- 如果它们匹配，则搜索成功，并返回目标值的索引。
- 如果目标值大于中间元素，则继续使用数据集的一半进行搜索。
- 如果目标值较小，则选择左半部分进行进一步探索。
二分查找非常高效，具有O(log n)的时间复杂度，其中n是数据集中的元素数量。这使得它成为大数据集中首选的方法，线性搜索是不可行的。然而，它要求数据集在进行搜索之前必须进行排序。
什么是二分查找？
二分查找是计算机科学和数学中广泛使用的算法，它在有序数据集中定位特定元素。它通过重复将数据集划分为两半，并将目标值与中间值进行比较，直到发现目标值或确定其不存在。
二分查找的工作原理是什么？
二分查找基于三个基本概念：有序数据、分治和搜索区域的减小。
有序数据
二分查找要求数据集按升序或降序排序。排序允许与中间元素进行系统比较，使算法能够确定目标值是在左侧还是右侧。
分治
二分查找采用分治策略。它从检查数据集的中间元素开始，将其分为两半。然后将中间元素与目标值进行比较。
- 如果它们匹配，则搜索成功。
- 如果目标值大于中间元素，则继续使用数据集的右半部分，丢弃左半部分。
- 如果目标值较小，则继续使用数据集的左半部分。
时间复杂度分析
- 在二分查找的每一步中，搜索空间减半。这意味着在一步之后只需要检查数据集的一半。
- 每一步，搜索区域都会减半。
- 这种方法会一直持续，直到找到目标值或搜索空间减少为空数据集，表示目标元素不存在。
二分查找的时间复杂度可以如下分析：
- 一步之后，搜索区域是N/2，其中N是元素数量。
- 两步之后，它是N/4。
- 三步之后，它是N/8，依此类推。
实现二分查找
二分查找的伪代码
BinarySearch(arr, target):
left = 0
right = arr的长度 - 1
while left <= right:
mid = (left + right) / 2
if arr[mid] == target:
return mid // 找到目标，返回其索引
else if arr[mid] < target:
left = mid + 1
Else:
right = mid - 1
Return -1 // 目标未找到。Python实现
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) / 2
if arr[mid] == target:
return mid # 找到目标，返回其索引
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 目标未找到处理边缘情况和特殊场景
- 空数组：如果输入数组为空，算法应返回-1，因为搜索没有元素。
- 目标不在数组中：如果目标值不在排序数组中，则算法返回-1。
- 重复值：二分查找适用于重复值。如果存在重复值，它将返回目标值的第一次出现的索引。
- 未排序的数组：二分查找假设输入数组已经排序。如果数组未排序，则算法将产生不正确的结果。请确保先对数组进行排序。
- 整数溢出：在某些编程语言（如C++）中，使用(left + right) / 2计算中间索引可能导致整数溢出，特别是对于非常大的left和right值。使用(left + (right-left)) / 2可以帮助避免这种情况。
- 浮点数误差：在使用浮点数运算的语言（如Python）中，对于较大的left和right值，使用(left + right) / 2可能不准确。在这种情况下，使用left + (right-left) / 2可以提供更好的结果。
数组中的二分查找
在编程中，对已排序数组执行二分查找是一项常见任务。以下是递归和迭代方法在已排序数组上执行二分查找的示例代码。
示例代码：Python中的迭代二分查找
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) /2
if arr[mid] == target:
return mid # 找到目标，返回其索引
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 未找到目标示例代码：Python中的递归二分查找
def binary_search_recursive(arr,target, left, right):
if left <= right:
mid = (left + right) / 2
if arr[mid] == target:
return mid # 找到目标，返回其索引
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
return -1 # 未找到目标解释
迭代方法
- 迭代二分查找从两个指针left和right开始。
- 它进入一个“while”循环，直到“left”小于或等于“right”。
- 在循环内部，它计算“mid”索引，并检查“mid”处的值是否等于目标。
- 如果找到目标，它返回索引。
- 如果目标小于“mid”处的元素，它将“right”更新为“mid – 1”，成功将搜索范围缩小到数组的左半部分。
- 如果目标更大，则将“left”更新为“mid + 1”，将搜索范围缩小到右半部分。
- 循环继续，直到找到目标或“left”大于“right”。
递归方法
- 递归二分查找使用“left”和“right”定义当前的搜索范围。
- 它检查“left”是否小于或等于“right”。
- 它计算“mid”索引并将“mid”处的元素与目标进行比较。
- 如果找到目标，它返回索引。
- 如果目标小于“mid”处的元素，它以更新的“right”值递归调用自身，搜索左半部分。
- 如果目标更大，它以更新的“left”值递归调用自身，搜索右半部分。
- 递归继续，直到找到目标或搜索空间为空。
其他数据结构中的二分查找
二分查找是一种有效的搜索算法，但其适应性取决于数据结构。
二叉搜索树（BSTs）
由于其结构，二叉搜索树是进行二分查找的自然类型。二叉搜索树是一种树，每个节点都有两个子节点，左子树包含小于当前节点的值的节点，右子树包含大于当前节点的值的节点。可以将二分查找适应于二叉搜索树，方法如下：
- 在二叉搜索树中搜索：从根节点开始，将目标值与当前节点的值进行比较。
- 如果它们匹配，搜索成功。
- 如果目标值较小，继续在左子树中进行搜索。
- 如果目标值较大，继续在右子树中进行搜索。
二叉搜索树的特别注意事项
- 在向二叉搜索树（BST）添加或删除元素时，保持BST的属性（对于每个节点，左子树的值小于当前节点的值，当前节点的值小于右子树的值）非常重要。
- 平衡树对于确保树的效率至关重要。不平衡的树可能会退化成链表，导致搜索时间变慢。
用例
BST在各种应用中使用，包括字典、数据库和符号表。
数组和列表
当数组和列表被排序时，二分查找可以适用于它们：
在数组或列表中进行搜索
在数组或列表中进行二分查找是一个基本的示例。数组或列表被视为一系列元素，并且算法进行处理。
特殊注意事项
- 数据结构必须被排序才能正确执行二分查找。
- 确保不要访问超出边界的指针。
用例
在数组或列表中进行二分查找在各种应用中使用，包括在已排序的数据库中搜索、在已排序的集合中查找元素以及优化归并排序和快速排序等算法。
处理重复值
处理二分查找中的重复值需要特定的策略来查找排序数据集中目标值的第一个、最后一个或全部出现次数。要查找第一个出现次数，执行标准的二分查找，并在找到目标时返回索引。要查找最后一个出现次数，修改二分查找，当找到目标时继续在右半部分进行搜索，以确保识别出最右边的出现次数。要查找所有出现次数，结合这两种策略，找到第一个或最后一个出现次数，并在两个方向上扩展搜索以收集所有指针。这样可以全面处理二分查找中的重复值。下面是使用Python代码示例说明这些技术来查找第一个、最后一个或所有出现次数：
第一个出现次数
def find_first_occurrence(arr, target):
left, right = 0, len(arr) - 1
result = -1 # 如果未找到目标，则将结果初始化为-1
while left <= right:
mid = (left + right) // 2 # 使用整数除法找到中点
if arr[mid] == target:
result = mid
right = mid - 1 # 继续在左半部分中搜索第一个出现次数
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result最后一个出现次数
def find_last_occurrence(arr, target):
left, right = 0, len(arr) - 1
result = -1 # 如果未找到目标，则将结果初始化为-1
while left <= right:
mid = (left + right) // 2 # 使用整数除法找到中点
if arr[mid] == target:
result = mid
left = mid + 1 # 继续在右半部分中搜索最后一个出现次数
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result所有出现次数
def find_all_occurrences(arr, target):
first_occurrence = find_first_occurrence(arr, target)
last_occurrence = find_last_occurrence(arr, target)
if first_occurrence == -1:
return [] # 未找到目标
else:
return [i for i in range(first_occurrence, last_occurrence + 1)]二分查找的变种
- 三分查找通过在两个等间距中点处评估目标与元素来将搜索空间分为三个元素。当处理具有单个最大或最小值的函数时，这种方法可能更高效，可以减少比较次数。
- 指数查找对于无界列表非常有用。它从小步长开始，指数级增加范围，直到找到边界，然后在该范围内应用二分查找。
二分查找的优化
优化二分查找算法涉及改进其整体增长和性能。策略包括跳跃搜索，通过固定步长预先跳跃，结合线性和二分搜索，在处理大型数组时减少比较次数。插值查找是另一种方法，它基于数据分布估计目标的位置，从而实现更快的收敛，特别适用于均匀分布的数据。
基准测试和分析对于优化大数据集上的二分查找至关重要。分析工具可以识别瓶颈，帮助调优代码。基准测试可以比较算法在不同情况下的执行时间，指导优化。这些技术确保二分查找在各种情况下都能达到最佳性能，无论是在数据库还是游戏开发等需要高效和快速的领域。
二分查找的常见错误和陷阱
- 未检查排序数据：在进行二分查找之前未确保数据已排序可能导致错误的结果。请始终验证数据已排序。
- 错误的中点计算：在一些语言中，使用（left + right）/ 2 来计算中点可能导致整数溢出或精度问题。请使用（left + (right-left)) / 2 来避免这些问题。
- 无限循环：在循环中未正确替换指针（left 和 right）可能导致无限循环。请确保定期更新它们。
实际应用
二分查找在计算机科学及其他领域中无处不在。它被用于像Google和Yahoo这样的搜索引擎以进行快速检索网页，用于高效查询的数据库，以及用于快速数据检索的文件系统。航空公司使用它来优化座位预订，并且在数据压缩算法中起着重要作用。
二分查找库和模块
许多流行的编程语言都提供了内置的库或模块，用于提供高效的二分查找实现。在Python中，“bisect”模块提供了诸如“bisect_left”，“bisect_right”和“bisect”之类的函数，用于在已排序列表中搜索和插入元素。
这些库函数经过优化，可以在编码自定义二分查找算法时节省时间和精力。
结论
二分查找是一种灵活高效的算法，用于快速查找已排序数据结构中的元素。它为优化各种应用提供了基础，从Google和Yahoo等搜索引擎到游戏开发。通过理解其原理并考虑不同的变体和库，开发者可以利用二分查找的优势成功和迅速地解决复杂问题。
如果您对此类算法感兴趣，我们的免费课程和博客可以帮助您很多。