二分查找

本章目标：彻底搞懂二分查找的边界处理，掌握二分答案（蓝红染色法）。

你将学到

• 二分查找的前提条件
• 闭区间/左闭右开/左开右闭三种写法
• 二分答案（在值域上二分）
• 浮点二分
• 旋转数组中的二分

1. 概念

二分查找要求：有序 + 随机访问。时间复杂度 O(log n)，是最基础的 logarithmic 算法。

但二分查找是面试中最容易写错的算法之一——循环条件是 < 还是 <=？mid 加 1 还是减 1？根本原因是对区间的定义不清晰。

推荐使用蓝红染色法（或称"左闭右开"统一写法）：把数组分成蓝色（满足某条件）和红色（不满足）两段，二分找到分界点。

2. 核心模板

标准二分查找（闭区间写法）

// 在有序数组中查找 target，返回下标，找不到返回 -1
func binarySearch(_ nums: [Int], _ target: Int) -> Int {
    var left = 0, right = nums.count - 1
    while left <= right {
        let mid = left + (right - left) / 2  // 防溢出
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

查找左边界（第一个 >= target）

// 蓝红染色法：left-1 为蓝色（<target），right+1 为红色（>=target）
func lowerBound(_ nums: [Int], _ target: Int) -> Int {
    var left = 0, right = nums.count  // 左闭右开 [0, n)
    while left < right {
        let mid = left + (right - left) / 2
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left  // left == right，第一个 >= target 的位置
}

二分答案模板

// 当答案具有单调性（满足条件的值连续），在值域上二分
// 例：将数组分成 m 段，使最大段和最小
func splitArray(_ nums: [Int], _ m: Int) -> Int {
    var lo = nums.max()!           // 下界：最大单个元素
    var hi = nums.reduce(0, +)     // 上界：所有元素之和
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if canSplit(nums, m, maxSum: mid) {
            hi = mid  // mid 可行，尝试更小
        } else {
            lo = mid + 1  // mid 不可行，需要更大
        }
    }
    return lo
}

func canSplit(_ nums: [Int], _ m: Int, maxSum: Int) -> Bool {
    var count = 1, curSum = 0
    for num in nums {
        if curSum + num > maxSum {
            count += 1
            curSum = num
            if count > m { return false }
        } else {
            curSum += num
        }
    }
    return true
}

复杂度

• 时间：O(log n)
• 空间：O(1)

3. 经典题目精讲

LeetCode 33 · 搜索旋转排序数组

题意：在旋转后的有序数组中查找目标值。

思路：每次二分，判断哪半部分是有序的，再决定搜索方向。

func search(_ nums: [Int], _ target: Int) -> Int {
    var left = 0, right = nums.count - 1
    while left <= right {
        let mid = left + (right - left) / 2
        if nums[mid] == target { return mid }
        // 左半有序
        if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            // 右半有序
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}

LeetCode 69 · x 的平方根

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

思路：在 0 到 x 上二分，找最大的 mid 使得 mid*mid <= x。

func mySqrt(_ x: Int) -> Int {
    if x <= 1 { return x }
    var left = 1, right = x
    while left <= right {
        let mid = left + (right - left) / 2
        if mid <= x / mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return right
}

LeetCode 410 · 分割数组的最大值

题意：将非负整数数组分成 m 个连续子数组，使最大子数组和最小。

思路：经典二分答案——答案在 [max(nums), sum(nums)] 之间，二分验证是否可行。

（代码见上方模板）

4. 易错点

• ⚠️ mid = (left + right) / 2 在某些语言中可能溢出，用 left + (right - left) / 2
• ⚠️ 闭区间用 left <= right + mid ± 1；左闭右开用 left < right + right = mid
• ⚠️ 旋转数组中判断有序时注意 <=（含等号），否则边界出错
• ⚠️ 二分答案时注意 lo 和 hi 的初始范围要覆盖所有可能答案

5. 推荐刷题清单

题号	题名	难度	关键
33	搜索旋转排序数组	Medium	旋转二分
34	在排序数组中查找范围	Medium	左右边界
69	x 的平方根	Easy	整数二分
153	寻找旋转排序数组最小值	Medium	旋转二分
162	寻找峰值	Medium	二分
410	分割数组的最大值	Hard	二分答案

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS)