跳到主要内容

二分查找

二分查找（Binary Search）是一种高效的查找算法，它利用数据的有序性，通过不断将搜索范围缩小一半来定位目标元素。其时间复杂度为 O(log⁡n)O(\log n)，空间复杂度为 O(1)O(1)。

虽然二分查找的思想可以用几句话解释清楚，但正确的实现却出人意料地容易出错。常见的问题包括：边界语义定义不清晰导致的差一错误、更新操作不能保证区间缩小导致的无限循环、以及大数溢出导致的中间点计算错误。因此，理解二分查找的关键在于建立清晰的不变量（Invariant）和正确的终止条件。

核心思想​

基本原理​

假设有一个有序数组，我们要查找目标值 target。二分查找的核心思路是：

  1. 维护一个搜索区间，目标值只可能出现在这个区间内
  2. 每次取区间中间位置的元素与目标值比较
  3. 根据比较结果，排除掉一半不可能包含答案的区间
  4. 重复以上步骤，直到找到目标值或区间为空

为什么能缩小一半？​

关键在于数组的有序性。假设中间位置的元素值为 mid：

  • 如果 mid < target，那么 mid 以及它左边的所有元素都小于 target，可以排除左半部分
  • 如果 mid > target，那么 mid 以及它右边的所有元素都大于 target，可以排除右半部分
  • 如果 mid == target，直接返回结果

每次比较后，搜索区间至少缩小一半，这就是 O(log⁡n)O(\log n) 时间复杂度的来源。

效率对比​

对于一个包含 n=220=1,048,576n = 2^{20} = 1,048,576 个元素的数组：

  • 线性查找最坏需要比较 1,048,576 次
  • 二分查找最坏只需要比较约 20 次

这种巨大的效率差异使得二分查找成为处理大规模有序数据的首选算法。

区间表示方法​

二分查找的实现细节很大程度上取决于如何表示搜索区间。常见的有两种方式：

闭区间 [left, right]​

  • left 和 right 都包含在搜索范围内
  • 区间为空的条件：left > right
  • 循环条件：left <= right
  • 更新规则：left = mid + 1 或 right = mid - 1

左闭右开区间 [left, right)​

  • left 包含，right 不包含
  • 区间为空的条件：left == right
  • 循环条件：left < right
  • 更新规则：left = mid + 1 或 right = mid

两种方式都可以正确实现二分查找，但闭区间的更新规则更加对称，更不容易出错，因此推荐使用闭区间方式。

基本模板​

闭区间实现​

/**
 * 二分查找（闭区间版本）
 * @param nums 有序数组
 * @param target 目标值
 * @return 目标值的索引，不存在返回 -1
 */
public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    // 区间 [left, right] 不为空时继续搜索
    while (left <= right) {
        // 防止溢出的中间点计算
        int mid = left + (right - left) / 2;

        if (nums[mid] < target) {
            // 目标在右半部分，排除 mid 及左边
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 目标在左半部分，排除 mid 及右边
            right = mid - 1;
        } else {
            // 找到目标值
            return mid;
        }
    }

    // 区间为空，目标不存在
    return -1;
}

左闭右开区间实现​

/**
 * 二分查找（左闭右开区间版本）
 */
public int binarySearchLCRO(int[] nums, int target) {
    int left = 0, right = nums.length;  // 注意：right 初始化为 length

    // 区间 [left, right) 不为空时继续搜索
    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] < target) {
            left = mid + 1;  // 排除 [left, mid]
        } else if (nums[mid] > target) {
            right = mid;     // 排除 [mid, right)
        } else {
            return mid;
        }
    }

    return -1;
}

两种实现的对比​

特性闭区间 [left, right]左闭右开 [left, right)
right 初始值nums.length - 1nums.length
循环条件left <= rightleft < right
区间为空条件left > rightleft == right
更新右侧right = mid - 1right = mid
对称性好（更新规则对称）稍差

中间点计算与溢出问题​

为什么不用 (left + right) / 2？​

当 left 和 right 都很大时（接近 Integer.MAX_VALUE），它们的和可能超出 int 类型的表示范围，导致溢出。溢出后的结果可能是负数，这会导致数组越界访问。

正确的计算方式​

int mid = left + (right - left) / 2;

这个公式在数学上等价于 (left + right) / 2，但避免了两个大数相加：

mid=⌊left+right−left2⌋=⌊left+right2⌋\text{mid} = \left\lfloor \text{left} + \frac{\text{right} - \text{left}}{2} \right\rfloor = \left\lfloor \frac{\text{left} + \text{right}}{2} \right\rfloor

由于 right - left 的值不超过数组长度，这个减法是安全的。

其他语言的技巧​

在 Java 中，还可以使用无符号右移：

int mid = (left + right) >>> 1;  // 无符号右移，相当于无符号除以 2

即使 left + right 溢出变成负数，无符号右移也能得到正确的中间值。但为了代码的可移植性和清晰性，推荐使用 left + (right - left) / 2。

循环不变量​

正确实现二分查找的关键是理解并维护循环不变量。以闭区间为例：

不变量定义​

在循环过程中，始终维护以下性质：

  1. 边界有效：0 <= left <= right + 1 <= n
  2. 左侧排除：对于所有 i < left，nums[i] < target
  3. 右侧排除：对于所有 i > right，nums[i] > target

这三个不变量共同说明：如果 target 存在于数组中，它一定在区间 [left, right] 内。

初始化​

设置 left = 0, right = n - 1：

  • 边界有效显然成立
  • 左侧和右侧排除条件"没有元素需要排除"，即空真（vacuously true）

维持不变量​

当 nums[mid] < target 时，更新 left = mid + 1：

  • 由于数组有序，nums[0..mid] 都小于 target
  • 新的 left 仍然满足"左侧排除"条件

当 nums[mid] > target 时，更新 right = mid - 1：

  • 由于数组有序，nums[mid..n-1] 都大于 target
  • 新的 right 仍然满足"右侧排除"条件

终止条件​

当循环结束时，left > right，区间为空。根据不变量：

  • 所有 i < left 的元素都小于 target
  • 所有 i > right（即 i >= left）的元素都大于 target

因此数组中不存在等于 target 的元素，返回 -1 是正确的。

边界查找​

当数组中存在重复元素时，我们可能需要找到第一个或最后一个等于 target 的位置。这就需要用到 lower_bound 和 upper_bound。

lower_bound：第一个大于等于 target 的位置​

lower_bound 返回第一个满足 nums[i] >= target 的索引，如果所有元素都小于 target，则返回 n。

/**
 * 查找第一个大于等于 target 的位置
 * @return 索引 i，使得 nums[i] >= target，若不存在则返回 nums.length
 */
public int lowerBound(int[] nums, int target) {
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] < target) {
            // mid 及左边都不满足条件
            left = mid + 1;
        } else {
            // mid 可能是答案，保留在区间内
            right = mid;
        }
    }

    return left;
}

理解要点：

  • 使用左闭右开区间 [left, right)
  • 当 nums[mid] >= target 时，不立即返回，而是继续向左收缩，寻找更早出现的位置
  • 最终 left 就是第一个满足条件的位置

upper_bound：第一个大于 target 的位置​

upper_bound 返回第一个满足 nums[i] > target 的索引。

/**
 * 查找第一个大于 target 的位置
 * @return 索引 i，使得 nums[i] > target，若不存在则返回 nums.length
 */
public int upperBound(int[] nums, int target) {
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] <= target) {
            // mid 及左边都不满足条件
            left = mid + 1;
        } else {
            // mid 可能是答案，保留在区间内
            right = mid;
        }
    }

    return left;
}

边界查找的应用​

通过 lower_bound 和 upper_bound，可以解决很多边界问题：

// 查找第一个等于 target 的位置
public int findFirst(int[] nums, int target) {
    int i = lowerBound(nums, target);
    if (i < nums.length && nums[i] == target) {
        return i;
    }
    return -1;
}

// 查找最后一个等于 target 的位置
public int findLast(int[] nums, int target) {
    int i = upperBound(nums, target) - 1;
    if (i >= 0 && nums[i] == target) {
        return i;
    }
    return -1;
}

// 统计 target 出现的次数
public int count(int[] nums, int target) {
    return upperBound(nums, target) - lowerBound(nums, target);
}

两种边界查找的对比​

方法条件返回值含义
lower_boundnums[i] >= target第一个 >= target 的位置
upper_boundnums[i] > target第一个 > target 的位置

两者配合使用可以精确定位 target 的所有出现位置。

二分答案​

二分答案是一种重要的算法技巧，也叫"答案二分"或"二分搜索空间"。当直接求解最优解很困难，但验证某个值是否可行很容易时，可以考虑二分答案。

适用场景​

满足以下条件的问题通常可以用二分答案解决：

  1. 答案具有单调性：如果 x 满足条件，那么比 x 更大（或更小）的值也满足或不满足条件
  2. 答案范围已知：答案的上界和下界可以确定
  3. 验证函数易写：给定一个值，能够快速判断它是否满足条件

问题特征​

这类问题常见的关键词：

  • "最小化最大值"
  • "最大化最小值"
  • "求...的最小值"
  • "求...的最大值"

经典例题：爱吃香蕉的珂珂​

题目（LeetCode 875）：给定 n 堆香蕉，每堆有 piles[i] 个。珂珂每小时可以选择一堆香蕉，最多吃 k 个。需要在 h 小时内吃完所有香蕉，求最小的 k。

分析：

  • 搜索空间：k 最小为 1，最大为 max(piles)（一次吃完最多的一堆）
  • 单调性：吃速越快，耗时越少。如果 k 能在 h 小时内吃完，那么所有大于 k 的值也一定能吃完
  • 验证函数：给定 k，计算吃完所有香蕉需要多少小时

代码实现：

public int minEatingSpeed(int[] piles, int h) {
    // 确定搜索范围
    int left = 1;
    int right = 0;
    for (int pile : piles) {
        right = Math.max(right, pile);
    }

    // 二分查找最小的 k
    while (left < right) {
        int mid = left + (right - left) / 2;

        if (canFinish(piles, mid, h)) {
            // mid 满足条件，尝试更小的值
            right = mid;
        } else {
            // mid 不满足条件，需要更大的值
            left = mid + 1;
        }
    }

    return left;
}

/**
 * 验证函数：判断能否在 h 小时内以速度 k 吃完所有香蕉
 */
private boolean canFinish(int[] piles, int k, int h) {
    int hours = 0;
    for (int pile : piles) {
        // 向上取整：(pile + k - 1) / k 等价于 ceil(pile / k)
        hours += (pile + k - 1) / k;
    }
    return hours <= h;
}

经典例题：分割数组的最大值​

题目（LeetCode 410）：将数组分割成 m 个连续子数组，使各子数组和的最大值最小。

分析：

  • 搜索空间：最大值最小为 max(nums)（每个元素单独成组），最大为 sum(nums)（整个数组作为一组）
  • 单调性：如果最大值 x 能分成不超过 m 组，那么更大的 x 也一定能做到
  • 验证函数：给定最大值 x，计算最少需要分几组

代码实现：

public int splitArray(int[] nums, int m) {
    int left = 0, right = 0;
    for (int num : nums) {
        left = Math.max(left, num);   // 最大元素
        right += num;                  // 总和
    }

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (canSplit(nums, mid, m)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

/**
 * 验证函数：判断能否将数组分成不超过 m 组，且每组和不超过 maxSum
 */
private boolean canSplit(int[] nums, int maxSum, int m) {
    int count = 1;  // 分组数
    int currentSum = 0;

    for (int num : nums) {
        if (currentSum + num > maxSum) {
            // 当前组放不下，开新组
            count++;
            currentSum = num;
            if (count > m) {
                return false;
            }
        } else {
            currentSum += num;
        }
    }

    return true;
}

二分答案的通用模板​

public int binarySearchAnswer(int[] nums, int condition) {
    // 1. 确定搜索范围
    int left = minPossible;   // 答案的最小可能值
    int right = maxPossible;  // 答案的最大可能值

    // 2. 二分查找
    while (left < right) {
        int mid = left + (right - left) / 2;

        // 3. 验证 mid 是否满足条件
        if (check(nums, mid, condition)) {
            // 满足条件，尝试更优解（根据题目要求调整方向）
            right = mid;  // 或 left = mid，取决于求最小还是最大
        } else {
            // 不满足条件，调整边界
            left = mid + 1;  // 或 right = mid - 1
        }
    }

    return left;
}

变体应用​

搜索旋转排序数组​

题目（LeetCode 33）：升序数组在某个点旋转后，查找目标值。

思路：旋转后的数组有一个特点：从中间切开，必有一部分是有序的。判断目标在有序部分还是无序部分，继续二分。

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        }

        // 判断哪一部分是有序的
        if (nums[left] <= nums[mid]) {
            // 左半部分有序
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // 右半部分有序
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;
}

搜索插入位置​

题目（LeetCode 35）：在有序数组中找到目标值的索引，如果不存在，返回它应该被插入的位置。

这其实就是 lower_bound 的定义：

public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

x 的平方根​

题目（LeetCode 69）：计算 x 的整数平方根（向下取整）。

思路：在 [0, x] 范围内二分查找最大的 mid，使得 mid * mid <= x。

public int mySqrt(int x) {
    if (x == 0) return 0;

    int left = 1, right = x;
    int result = 0;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 使用除法避免溢出
        if (mid <= x / mid) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

注意：这里用 mid <= x / mid 而不是 mid * mid <= x，是为了避免 mid * mid 溢出。

寻找峰值​

题目（LeetCode 162）：数组中相邻元素不相等，找到任意一个峰值元素（大于相邻元素）。

思路：如果 nums[mid] < nums[mid + 1]，说明峰值在右边；否则在左边。

public int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] < nums[mid + 1]) {
            // 上升坡，峰值在右边
            left = mid + 1;
        } else {
            // 下降坡或山顶，峰值在左边（包括 mid）
            right = mid;
        }
    }

    return left;
}

寻找重复数​

题目（LeetCode 287）：数组包含 n + 1 个元素，值在 [1, n] 范围内，找出唯一的重复数。

思路：二分答案。统计数组中 <= mid 的元素个数，如果个数大于 mid，说明重复数在 [1, mid] 范围内。

public int findDuplicate(int[] nums) {
    int left = 1, right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        // 统计 <= mid 的元素个数
        int count = 0;
        for (int num : nums) {
            if (num <= mid) {
                count++;
            }
        }

        if (count > mid) {
            // 重复数在左半部分
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

常见陷阱​

1. 中间点计算溢出​

错误写法：

int mid = (left + right) / 2;  // 可能溢出

正确写法：

int mid = left + (right - left) / 2;

2. 边界更新导致无限循环​

错误写法：

// 左闭右开区间
while (left < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] > target) {
        right = mid - 1;  // 错误：应该用 right = mid
    }
    // ...
}

左闭右开区间下，right 本身不包含在区间内，如果 nums[mid] > target，应该设置 right = mid 而不是 mid - 1。

3. 循环条件错误​

闭区间和左闭右开区间的循环条件不同：

区间类型循环条件区间为空条件
[left, right]left <= rightleft > right
[left, right)left < rightleft == right

4. 返回值错误​

查找左边界时，最终的 left 可能越界或指向不等于 target 的元素：

// 错误：直接返回 left，没有检查
public int findFirst(int[] nums, int target) {
    // ... 二分查找 ...
    return left;  // 可能 nums[left] != target 或 left == nums.length
}

// 正确：检查返回值
public int findFirst(int[] nums, int target) {
    // ... 二分查找 ...
    if (left < nums.length && nums[left] == target) {
        return left;
    }
    return -1;
}

5. 乘法溢出​

在计算平方或乘积时注意溢出：

// 错误
if (mid * mid <= x) { ... }

// 正确
if (mid <= x / mid) { ... }

最佳实践​

1. 选择合适的区间类型​

  • 闭区间：推荐新手使用，更新规则对称，不易出错
  • 左闭右开：适合边界查找（lower_bound/upper_bound），与 C++ STL 风格一致

2. 明确搜索目标​

在写代码前，明确要找的是什么：

  • 任意一个等于 target 的位置 → 基本二分
  • 第一个等于 target 的位置 → lower_bound 后检查
  • 最后一个等于 target 的位置 → upper_bound - 1 后检查
  • 满足某条件的最小值 → 二分答案

3. 使用不变量推导​

遇到不确定的边界更新时，用不变量来验证：

  • 更新后，区间是否缩小？
  • 更新后，答案是否仍在区间内？

4. 处理边界情况​

特别关注：

  • 空数组
  • 单元素数组
  • 目标小于所有元素
  • 目标大于所有元素
  • 目标等于第一个/最后一个元素

时间与空间复杂度​

时间复杂度​

  • 查找操作：O(log⁡n)O(\log n)
  • 每次迭代：O(1)O(1)（比较和更新）
  • 总迭代次数：⌈log⁡2n⌉\lceil \log_2 n \rceil

空间复杂度​

  • 迭代版本：O(1)O(1)
  • 递归版本：O(log⁡n)O(\log n)（递归调用栈）

与其他查找算法的对比​

算法时间复杂度空间复杂度前提条件
线性查找O(n)O(n)O(1)O(1)无
二分查找O(log⁡n)O(\log n)O(1)O(1)有序
哈希查找O(1)O(1) 平均O(n)O(n)无

二分查找在空间效率上优于哈希查找，但需要数据有序。

适用场景与局限性​

适用场景​

  1. 数据有序：数组或可以随机访问的有序数据结构
  2. 静态数据：数据不频繁变动，或变动代价可接受
  3. 大规模数据：数据量大时，对数级查找优势明显

局限性​

  1. 要求数据有序：无序数据需要先排序，排序成本 O(nlog⁡n)O(n \log n)
  2. 仅支持随机访问：链表等顺序访问结构不适合
  3. 小规模数据不占优：数据量小时，线性查找可能更快（因为常数因子更小）

小结​

二分查找是一种简洁但精妙的算法。掌握它的关键在于：

  1. 理解不变量：明确搜索区间的含义，确保每次更新后不变量成立
  2. 注意边界：区间类型决定循环条件和更新规则
  3. 避免溢出：使用 left + (right - left) / 2 计算中间点
  4. 灵活应用：不仅限于数组查找，还适用于答案二分等场景

二分查找的代码很短，但细节很多。建议在理解原理的基础上，选择一种自己熟悉的模板（推荐闭区间），反复练习，形成肌肉记忆。

练习​

基础：

  1. LeetCode 704：二分查找
  2. LeetCode 35：搜索插入位置
  3. LeetCode 69：x 的平方根
  4. LeetCode 367：有效的完全平方数

边界查找：5. LeetCode 34：在排序数组中查找元素的第一个和最后一个位置6. LeetCode 744：寻找比目标字母大的最小字母

旋转数组：7. LeetCode 33：搜索旋转排序数组 8. LeetCode 81：搜索旋转排序数组 II 9. LeetCode 153：寻找旋转排序数组中的最小值 10. LeetCode 154：寻找旋转排序数组中的最小值 II

二分答案：11. LeetCode 875：爱吃香蕉的珂珂 12. LeetCode 410：分割数组的最大值 13. LeetCode 1011：在 D 天内送达包裹的能力 14. LeetCode 1482：制作 m 束花所需的最少天数

其他变体：15. LeetCode 162：寻找峰值16. LeetCode 287：寻找重复数17. LeetCode 374：猜数字大小18. LeetCode 278：第一个错误的版本

进阶：19. LeetCode 4：寻找两个正序数组的中位数 20. LeetCode 658：找到 K 个最接近的元素