抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

算法-二分查找

算法

发布于：2025年4月8日

字数：3.2k 字

时长：12 分钟

前言

在算法领域，二分查找（Binary Search）凭借其优雅的思路和高效的性能，成为解决查找问题的关键技术。本文将深入探讨二分查找的核心思想、实现细节、常见变种以及实际应用，并通过丰富的例题帮助读者真正掌握这一算法精髓。

基本原理

二分查找是一种在有序数组中查找特定元素的高效算法。其核心思想是：通过将搜索区间反复折半，每次比较中间元素与目标值的大小关系，从而快速缩小搜索范围。

基本步骤

  1. 确定初始搜索区间 [left, right]
  2. 当 left <= right 时，计算中间位置 mid = left + (right - left) // 2
  3. 比较中间元素 arr[mid] 与目标值 target：
    • 若相等，返回索引 mid
    • 若 target < arr[mid]，在左半部分继续查找，令 right = mid - 1
    • 若 target > arr[mid]，在右半部分继续查找，令 left = mid + 1
  4. 若最终 left > right，表示未找到目标值，返回 -1 或其他适当的标记

时间复杂度分析

每次迭代将搜索空间缩小一半，因此时间复杂度为 $O(log n)$，这比线性搜索的 $O(n)$ 要高效得多。正是这种对数级的复杂度，使得二分查找能够处理大规模数据集的查找问题。

基本实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # 防止整数溢出
        
        if arr[mid] == target:
            return mid  # 找到目标值，返回索引
        elif arr[mid] < target:
            left = mid + 1  # 目标在右半部分
        else:
            right = mid - 1  # 目标在左半部分
    
    return -1  # 未找到目标值

常见变种

在实际应用中，我们经常需要处理比简单查找更复杂的场景。以下是几种常见的二分查找变种及其实现。

查找第一个等于目标值的元素

当数组中存在多个相同值时，标准二分查找可能返回任意一个匹配的索引。要查找第一个等于目标值的元素，需要在找到匹配元素后继续向左搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search_first_equal(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] >= target:  # 关键区别：找到目标后继续往左找
            right = mid - 1
            if arr[mid] == target:
                result = mid  # 记录当前找到的位置
        else:
            left = mid + 1
    
    return result

查找最后一个等于目标值的元素

类似地，要查找最后一个等于目标值的元素，需要在找到匹配元素后继续向右搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search_last_equal(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:  # 关键区别：找到目标后继续往右找
            left = mid + 1
            if arr[mid] == target:
                result = mid  # 记录当前找到的位置
        else:
            right = mid - 1
    
    return result

查找第一个大于等于目标值的元素

这种变种在实现上下界查询和范围搜索时非常有用。

1
2
3
4
5
6
7
8
9
10
11
12
13
def binary_search_first_ge(arr, target):
    left, right = 0, len(arr) - 1
    result = len(arr)  # 如果所有元素都小于target，返回数组长度
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] >= target:
            result = mid  # 记录当前位置
            right = mid - 1  # 继续查找可能存在的更小索引
        else:
            left = mid + 1
    
    return result

查找最后一个小于等于目标值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
def binary_search_last_le(arr, target):
    left, right = 0, len(arr) - 1
    result = -1  # 如果所有元素都大于target，返回-1
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            result = mid  # 记录当前位置
            left = mid + 1  # 继续查找可能存在的更大索引
        else:
            right = mid - 1
    
    return result

在旋转有序数组中查找

旋转数组是指将有序数组的前面一部分移到末尾形成的数组，如 [4,5,6,7,0,1,2]。在这种特殊情况下，二分查找需要额外判断哪一侧是有序的，然后决定在哪一侧继续查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def search_in_rotated(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        
        # 判断哪一侧是有序的
        # 左侧有序
        # 等号：考虑 left==mid，即只有一个元素的情况
        if arr[left] <= arr[mid]:   
            # 加等号，因为 left 可能是 target；mid 已经比较过了，加不加都无所谓
            if arr[left] <= target < arr[mid]:
                right = mid - 1  # 目标在左侧有序部分
            else:
                left = mid + 1  # 目标在右侧
        else:  # 右侧有序
            # 加等号，因为 right 可能是 target；mid 已经比较过了，加不加都无所谓
            if arr[mid] < target <= arr[right]:
                left = mid + 1  # 目标在右侧有序部分
            else:
                right = mid - 1  # 目标在左侧
    
    return -1  # 未找到

例题解析

例题1：基本二分查找 - 力扣 704. 二分查找

示例：

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
def search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

分析：这是最基本的二分查找应用，直接使用标准模板即可。关键是理解二分查找的终止条件和区间更新方式。

例题2：查找第一个等于目标值的元素 - 力扣 34. 在排序数组中查找元素的第一个和最后一个位置

题目描述：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值，返回 [-1, -1]。

示例：

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def searchRange(nums, target):
    # 查找第一个位置
    def searchFirst(nums, target):
        left, right = 0, len(nums) - 1
        result = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid - 1
                if nums[mid] == target:
                    result = mid
            else:
                left = mid + 1
        
        return result
    
    # 查找最后一个位置
    def searchLast(nums, target):
        left, right = 0, len(nums) - 1
        result = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
                if nums[mid] == target:
                    result = mid
            else:
                right = mid - 1
        
        return result
    
    first = searchFirst(nums, target)
    last = searchLast(nums, target)
    
    return [first, last]

分析：这道题目需要分别查找第一个等于目标值的元素和最后一个等于目标值的元素，是二分查找变种的典型应用。关键在于理解找到目标值后，仍然需要继续搜索以确定边界。

例题3：旋转数组中的查找 - 力扣 33. 搜索旋转排序数组

题目描述：整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）处进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]。例如，[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]。给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。

示例：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        
        # 判断哪一侧是有序的
        if nums[left] <= nums[mid]:  # 左侧有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1  # 目标在左侧有序部分
            else:
                left = mid + 1  # 目标在右侧
        else:  # 右侧有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1  # 目标在右侧有序部分
            else:
                right = mid - 1  # 目标在左侧
    
    return -1  # 未找到

分析：这道题的难点在于如何处理旋转后的数组。关键思路是：虽然整个数组不是完全有序的，但分成两部分后，至少有一部分是有序的。我们可以先判断哪一部分是有序的，然后判断目标值是否在有序部分范围内，据此决定下一步搜索的区间。

例题4：查找平方根 - 力扣 69. x 的平方根

题目描述：实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例：

1
2
3
输入: 8
输出: 2
解释: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def mySqrt(x):
    if x == 0:
        return 0
    
    left, right = 1, x
    result = 0
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if mid <= x // mid:  # 避免mid*mid可能的溢出
            result = mid  # 记录当前结果
            left = mid + 1  # 尝试找更大的值
        else:
            right = mid - 1
    
    return result

分析：这道题实际上是在查找最后一个平方不大于 x 的整数，是”查找最后一个小于等于目标值的元素”的变种。使用二分查找可以高效地逼近平方根。注意到 mid * mid 可能导致整数溢出，因此使用等价的 mid <= x // mid 条件来避免溢出。

例题5：寻找峰值 - 力扣 162. 寻找峰值

题目描述：峰值元素是指大于左右相邻值的元素。给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。假设 nums[-1] = nums[n] = -∞。

示例：

1
2
3
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[mid + 1]:
            # 峰值在左半部分或者就是mid
            right = mid
        else:
            # 峰值在右半部分
            left = mid + 1
    
    return left  # 此时left == right，指向峰值位置

分析：这道题展示了二分查找在非传统场景下的应用。我们利用数组中的”上升”和”下降”趋势来确定峰值的位置。当 nums[mid] > nums[mid + 1] 时，说明 mid 可能是峰值或峰值在左侧；否则，峰值一定在右侧。这种二分查找的判断条件非常巧妙，值得学习。

实际应用场景

二分查找及其变种在众多实际应用中发挥着重要作用：

  1. 数据库索引查询：B树和B+树等数据库索引结构中的查找操作本质上是二分查找的多路扩展。

  2. IP路由表查找：路由器需要快速找到目的IP地址的最长前缀匹配，实质上是变种的二分查找问题。

  3. 机器学习中的超参数优化：使用二分查找或更复杂的算法如贝叶斯优化来高效探索超参数空间。

  4. 图像处理中的边缘检测：在某些边缘检测算法中，二分查找可用于快速定位梯度变化最大的点。

  5. 计算数值近似解：计算平方根、立方根等数值问题可以使用二分法逼近。

  6. 负载均衡算法：在分布式系统中，一致性哈希等负载均衡算法使用二分查找或其变种来定位服务器节点。

后记

二分查找看似简单，实则蕴含深刻的算法思想。它的核心是”不断缩小搜索空间”，这一思想可推广到许多其他算法中。熟练掌握二分查找及其变种，将为解决更复杂的算法问题打下坚实基础。

在实际应用中，需要特别注意以下几点：

  1. 边界条件：循环条件是 left <= right 还是 left < right？更新规则是 mid + 1 还是 mid？这些细节会直接影响算法的正确性。

  2. 整数溢出：计算中间索引时，应使用 mid = left + (right - left) // 2 而非 mid = (left + right) // 2，以避免整数溢出。

  3. 空间复杂度：标准的二分查找是原地操作，空间复杂度为 $O(1)$，这是它的一个重要优势。

  4. 适用性：二分查找要求数据集是有序的。对于无序数据，需要先排序（$O(n log n)$）再查找，此时可能不如直接线性搜索。

希望本文能帮助读者真正理解二分查找的精髓，并在实际问题中灵活运用这一强大的算法工具。通过反复练习本文中的例题，相信大家能够熟练掌握二分查找的各种变种和技巧。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://blog.skyheart.moe/posts/a59a04ac/

更新于：2025年4月8日

二分查找

评论