博客

详解二分查找算法原理与使用方法

二分查找算法详解

什么是二分查找算法？

二分查找是一种在有序数组中查找指定值的算法。该算法通过将待查找的区间不断缩小为原来的一半，直到找到目标值或者确定目标值不存在为止。由于每次迭代都将待查找区间减半，因此该算法的时间复杂度为 $O(\log n)$。

二分查找的使用场景

二分查找适用于有序数组中查找单个元素（也可用于查找多个元素），在这些情况下，二分查找通常比线性查找更优。比如在查找邮编、电话号码等固定格式数据时，我们可以利用二分查找算法。

二分查找的实现

迭代实现

二分查找算法的迭代实现通常采用循环的方式实现，具体过程如下：

  1. 将区间的左右边界分别设置为 $left$ 和 $right$；
  2. 当 $left <= right$ 时执行下面的步骤，并在循环中判断是否找到元素；
  3. 将区间的中间位置 $mid$ 置为 $left$ 和 $right$ 的平均数，即 $mid = (left + right) / 2$；
  4. 如果 $a[mid] == target$，说明找到了目标元素，返回 $mid$；
  5. 如果 $a[mid] > target$，说明目标元素在左半部分，将 $right$ 更新为 $mid – 1$；
  6. 如果 $a[mid] < target$，说明目标元素在右半部分，将 $left$ 更新为 $mid + 1$；
  7. 如果循环结束仍未返回，说明数组中不存在目标元素，返回 $-1$。

下面是迭代实现的代码示例：

def binary_search_iterative(a, target):
    left, right = 0, len(a) - 1
    while left <= right:
        mid = (left + right) // 2
        if a[mid] == target:
            return mid
        elif a[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return -1

递归实现

除了迭代实现外，二分查找算法还可以采用递归的方式实现，具体过程如下：

  1. 将区间的左右边界分别设置为 $left$ 和 $right$；
  2. 当 $left > right$ 时返回 $-1$；
  3. 将区间的中间位置 $mid$ 置为 $left$ 和 $right$ 的平均数，即 $mid = (left + right) / 2$；
  4. 如果 $a[mid] == target$，说明找到了目标元素，返回 $mid$；
  5. 如果 $a[mid] > target$，说明目标元素在左半部分，递归查找左半部分；
  6. 如果 $a[mid] < target$，说明目标元素在右半部分，递归查找右半部分。

下面是递归实现的代码示例：

def binary_search_recursive(a, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if a[mid] == target:
        return mid
    elif a[mid] > target:
        return binary_search_recursive(a, target, left, mid - 1)
    else:
        return binary_search_recursive(a, target, mid + 1, right)

二分查找的应用示例

查找元素

假设有一个已排序的数组 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，我们要查找其中的元素 5。使用迭代实现的二分查找算法，代码如下：

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 5
result = binary_search_iterative(a, target)
if result != -1:
    print(f"元素 {target} 的索引为 {result}")
else:
    print(f"数组中不存在元素 {target}")

上述代码输出的结果为：

元素 5 的索引为 4

重复元素处理

如果待查找的数组中存在重复元素，二分查找算法通常只能查找到其中一个元素的位置。假设数组 [1, 2, 3, 3, 3, 4, 5, 6, 7, 8] 中有多个值为 3 的元素，我们通过迭代实现的二分查找算法查找元素 3，代码如下：

a = [1, 2, 3, 3, 3, 4, 5, 6, 7, 8]
target = 3
left, right = 0, len(a) - 1
while left <= right:
    mid = (left + right) // 2
    if a[mid] >= target:
        right = mid - 1
    else:
        left = mid + 1
start_index = left
left, right = 0, len(a) - 1
while left <= right:
    mid = (left + right) // 2
    if a[mid] <= target:
        left = mid + 1
    else:
        right = mid - 1
end_index = right
if start_index <= end_index:
    print(f"元素 {target} 在数组中出现的次数为 {end_index - start_index + 1}")
else:
    print(f"数组中不存在元素 {target}")

上述代码输出的结果为：

元素 3 在数组中出现的次数为 3

上述代码中的 start_index 和 end_index 分别表示元素 3 在数组中第一次出现的索引和最后一次出现的索引。最终我们可以通过 end_index - start_index + 1 来计算出元素 3 在数组中出现的次数。

结语

二分查找算法是一种高效的查找算法，在有序数组中常常会被使用。我们通常可以通过迭代和递归两种方式来实现二分查找算法，同时也需要注意到二分查找算法在查找重复元素时的处理方法。

Tags: