二分搜索

EricYuan 收录于类别 Algorithm 和系列 Trick 阅读量次

2023-01-03 2024-02-25 约 2469 字预计阅读 12 分钟

系列 -

二分法适用条件

一开始，我简单地认为是数据需要具有单调性，才能应用二分；后来刷了一部分题之后，才晓得，应用二分的本质是数据具有**二段性**，即：一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。

重点理解！！！

循环不变式

while low <= high
1. 终止条件，一定是 low + 1 == high，也即 low > right
2. 意味着，整个区间 [low..high] 里的每个元素都被遍历过了
while low < high
1. 终止条件，一定是 low == high
2. 意味着，整个区间 [low..high] 里当 low == high 时的元素可能会没有被遍历到，需要打个补丁
3. 补充：如 lc.153，采用逼近策略寻找答案时，两指针最后指向相同位置，如过这个位置的元素不用拿出来做什么操作，只是找到它就行，那么就用 < 也是合适的。

可行解区间

对于二分搜索过程中的每一次循环，它的可行解区间都应当一致，结合对于循环不变式的理解：

[low...high]，左右都闭区间，一般根据 mid 就能判断下一个搜索区间是 low = mid + 1 还是 high = mid - 1
[low...high)，左闭右开区间，维持可行解区间，下一个搜索区间左边是 low = mid + 1，右边是 high = mid

因为数组的特性，常用的就是这两种区间。当然也有左右都开的区间 (low...high)，对应的循环不变式为 while low + 1 < high，不过比较少见。

另外请务必理解可行解区间到底是个啥！不是说定义了指针为 low = 0, high = len - 1，就代表着可行解区间为 [low...high]，而是需要看实际题意。比如，你能确定 low = 0 指针和 high = len - 1 指针的解一定不在我需要的结果之中，那么对应的可行解区间就是 (low...high)，相应的就可以使用 while low + 1 < high 的循环不变式

对于寻找左右边界的问题，也是根据可行解区间，去决定 low 或 high 的每一轮 update。搜索左侧边界：mid == x 时 r = mid; 搜索右侧边界： mid == x 时，l = mid + 1，需要注意，搜索右边界结束时 l = mid + 1，所以搜索数据的真实位置是 l - 1 。

练习

lc.33 搜索旋转排序数组

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    let l = 0,
        r = nums.length - 1
    while (l <= r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] < nums[l]) {
            // 右半边有序的情况
            if (nums[mid] < target && target <= nums[r]) {
                l = mid + 1
            } else {
                r = mid - 1
            }
        } else {
            // 左半边有序的情况 target 在有序区间内
            if (nums[l] <= target && target < nums[mid]) {
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
    }
    return -1
}

/**
 * 来看一下，如果用开闭右开区间的方式，怎么改写代码
 */
var search = function (nums, target) {
    let l = 0,
        r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] > nums[l]) {
            // 左半边有序的情况 target 在有序区间内
            if (nums[l] <= target && target < nums[mid]) {
                r = mid
            } else {
                l = mid + 1
            }
        } else {
            // 右半边有序的情况
            /**
             * 这里需要格外注意!!!，因为右边界是开区间，所以比较的是 nums[r - 1]
             */
            if (nums[mid] < target && target <= nums[r - 1]) {
                l = mid + 1
            } else {
                r = mid
            }
        }
    }
    return -1
}

lc.34 在排序数组中查找元素的第一个和最后一个位置

比上一题还简单~

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
    // 就是寻找左右边界
    const res = []
    let l = 0,
        r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] < target) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    if (nums[l] !== target) return [-1, -1] // 注意点，记得判断是否存在target
    res[0] = l
    l = 0
    r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] > target) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    res[1] = r - 1 // 因为我使用的是左闭右开区间，最终取右边界 - 1 即可
    return res
}
/**
 * 对于求边界的二分，如果用左右都闭的形式，需要在 while 后判断一下 l、r 是否在区间内
 * 因为 l <= r 的结束条件是 l + 1 = r，有可能产生越界情况，
 * 这道题恰好是题目要求了，所以做了个判断
 */

在判断 nums[mid] 和 target 的大小来进行决策的时候，我的习惯是看 target 在 mid 的左边还是右边，这样就更直观一些。比如： nums[mid] > target，直观理解应该是 mid 在 target 的右边，这时候可能一下子有点懵，是去收缩左边还是收缩右边（可能我比较菜）😂 如果转换为 target 在 mid 的左边，脑补一下就能想得到要去左边寻找，所以要收缩右边界。

lc.35 搜索插入位置 easy

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
    let l = 0,
        r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] > target) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

比较普通的一题，我看了官解和评论后，有人问找到 target 后为什么不直接返回（官解是没有返回的），仔细看了下题目，因为题目中规定了 nums 中不会有重复的元素，所以，按道理说是可以直接返回的，官解是考虑到了有重复元素的情况，变成了寻找左边界去了。

lc.74 搜索二维矩阵

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    let l = 0,
        r = matrix.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (matrix[mid][0] === target) {
            return true
        } else if (matrix[mid][0] > target) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    // 因为寻找的是 第一个 >= target 的，即寻找第一列的右边界
    if (r - 1 < 0) return false

    const row = matrix[l - 1]
    let i = 0,
        j = row.length
    while (i < j) {
        const mid = i + ((j - i) >> 1)
        if (row[mid] === target) {
            return true
        } else if (row[mid] > target) {
            j = mid
        } else {
            i = mid + 1
        }
    }
    return false
}

lc.81 搜索旋转排序数组 II

对比 lc.33 题只是多了重复的元素，问题是，如过旋转点恰好是重复的元素，就会使得数据丧失「二段性」：

https://cdn.jsdelivr.net/gh/yokiizx/picgo@main/img/202402232329422.png

官解的做法是恢复二段性即可：if(nums[l] == nums[mid] && nums[mid] == nums[r]) {l++, r--}

偷懒点就只收缩一边也行的，左边或右边都行，比如我选择了当 nums[l] === nums[mid] 时，收缩左边界

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function (nums, target) {
    let l = 0,
        r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] === target) {
            return true
        } else if (nums[mid] > nums[l]) {
            if (nums[l] <= target && target < nums[mid]) {
                r = mid
            } else {
                l = mid + 1
            }
        } else if (nums[mid] < nums[l]) {
            if (nums[mid] < target && target <= nums[r - 1]) {
                l = mid + 1
            } else {
                r = mid
            }
        } else {
            // nums[mid] === nums[l] 情况 收缩左边界目的是恢复 二段性
            l++
        }
    }
    return false
}

/** 再来看看收缩右边界的情况 */
var search = function (nums, target) {
    let l = 0,
        r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] === target) {
            return true
        } else if (nums[mid] < nums[r - 1]) {
            if (nums[mid] < target && target <= nums[r - 1]) {
                l = mid + 1
            } else {
                r = mid
            }
        } else if (nums[mid] > nums[r - 1]) {
            if (nums[l] <= target && target < nums[mid]) {
                r = mid
            } else {
                l = mid + 1
            }
        } else if (nums[mid] === nums[r - 1]) {
            r--
        }
    }
    return false
}

/** 两边同时收缩的看官解吧~ */

收缩左边界，就让 mid 和左侧比；收缩右边界，就让 mid 和右侧的比

lc.153 寻找旋转排序数组中的最小值

说实话，这道题一开始困扰了我很久 😭，因为它有点与众不同~

当时我是这么分析的（以下的 mid 代表 nums[mid], l 代表 nums[l]）：

如果，数组 n 次旋转后，单调有序，最小值就是最左边的
如果，数组 n 次旋转后，无序，则最小值就在二分后无序的那半边了
- 2.1 mid > l，右半边无序，选择右半边（坑）
- 2.2 mid < l，左半边无序，选择左半边

死活有那个几个用例过不了~ 看了题解，是跟右侧比较的 😭 why？？？跟左侧比有啥不一样嘛？后来仔细想了下，问题出在了 2.1 mid > l 右边无序，第一条就是最好的反例，此时最小值在最左边得选择左半边了，因此，mid 与 l 比较是满足不了二段性的，而与 r 比较就不一样了：

mid > r，则右侧无序，选择右侧，忽略左边
mid < r，则若左侧无序，选择左侧，忽略右边；若左侧有序，r 持续收缩逼近，也能得到结果，所以也可以选择左侧
- 也可以这么想：mid < r，右侧有序，则结果一定在 [l..mid] 中

因此，mid 与 r 比较能满足二段性。(PS：mid 想要与 l 比较也是可以的，二分前先排除掉整个数据单调不就好了，此处就不拓展了)

再思考一下，如果求最大值呢？😁，那就应该是不断收缩 l 去逼近，就适合用 mid 和 l 做比较了。

接下来还有第二个坑 😭

最初初始化右侧边界用的 r === nums.length，我寻思就跟之前一样，用左闭右开区间得了，不料却有测试用例没有过去 — [4,5,1,2,3]，这是为啥呢，带进去一看，原来是 mid 恰好为最小值时，r 更新为 mid，但是遍历却并没有停止，l 仍然是小于 r 的，然后就会走到错误的答案去了。

可是为什么之前这样写就没啥问题呢？我又思考了下，奥，之前都是给一个目标 target，会有判断 nums[mid] === target 的情况，命中直接 return；而这里是无目标的，只能让双指针不断逼近从而得到最后的结果。根据前面的分析 r 的 update 策略为 r = mid，麻烦就在这里了，再来看一下它的两层含义：

r == mid 的第一层含义，左侧无序，舍去右侧，但此时的 mid 有可能为可行解，所以 r 不能等于 mid -1
r == mid 的第二层含义，左侧有序，不断逼近，此时 r == mid， 每次逼近的值都有可能为可行解，这就与 [l..r) 的可行解区间不符了

因此可行解区间设为 [l..r] 是符合要求的，所以初始化为 r = nums.length - 1。（我隐约觉得这背后一定是有某种数学逻辑，求大佬赐教）

/** 错误解法 */
var findMin = function (nums) {
    let l = 0,
        r = nums.length // bug
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] > nums[r - 1]) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return nums[r]
}
/**
 * [2,1] 举例
 * 1. l == 0, r == 2, mid = 1, nums[1] > nums[1] : false --> r = 1
 * 2. l == 0, r == 1，mid = 0, nums[0] > nums[0] : false --> r = 0
 * 结束循环 l == r == 0
 *
 * 会发现，一旦数据巧合了后，就一直进入 nums[mid] 和 nums[mid] 自身比较的情况了
 */

/** 修改后 */
var findMin = function (nums) {
    let l = 0,
        r = nums.length - 1
    // 由此可见，用 < 还是 <= 完全取决于题意，它只是用来控制遍历的结束时机，
    // 在这里，当 l == r 时，就是解，所以 < 即可，（因为不需要对最后一个元素做什么操作）
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        // 右侧无序
        if (nums[mid] > nums[r]) {
            l = mid + 1
        } else {
            // 否则右侧有序 结果就肯定在 [l..mid] 中，所以 r = mid
            r = mid
        }
    }
    return nums[r]
}
/**
 * [2,1] 举例
 * 1. l == 0, r == 1, mid = 0, nums[0] > nums[1] : true --> l = mid + 1 === 1
 * 结束循环 l == r == 1
 */

那通过这道题能积累的经验是：

务必要分析好题目的二段性，正确的去选择左右分区，同时注意可行解区间在每一轮中是否保持一致
当无目标，根据双指针去探测极值的时候，使用 [l..r] 的闭区间较为稳妥
再回过头来结合 l.81 题，旋转数组寻找极小值，就是选择无序区间，然后再无序区间内寻找到有序区间，在有序区间内（单调增），那肯定是从右往左收缩，所以和右侧比没毛病；假如是搜索极大值，那么就是和左侧比了。

lc.154 寻找旋转排序数组中的最小值 III hard

相比 lc.153 就是多了重复元素，纸老虎罢了。

var findMin = function (nums) {
    let l = 0,
        r = nums.length - 1
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] > nums[r]) {
            l = mid + 1
        } else if (nums[mid] < nums[r]) {
            r = mid
        } else {
            // nums[mid] === nums[r]
            r--
        }
    }
    return nums[r]
}

注意：在 lc.153 题里也有 nums[mid] === nums[r] 的判断，只是因为 153 题保证了数据不是重复的，从而直接把 r = mid 即可，当遇到有重复数据的时候，就不能这么做了，即再参考 lc.81 题，重复数据恰好在旋转点的时候，会丧失二段性，解法也是类似的。

lc.162 寻找峰值

解法和 lc.153 简直如出一辙，只是从比较 mid 和 r 变为比较 mid 和 mid+1。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function (nums) {
    let l = 0,
        r = nums.length - 1
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        /**
         * mid > mid + 1，所以 mid 可能为极大值 r = mid
         * 否则  mid <= mid + 1, mid < mid + 1 时， l = mid + 1, mid = mid + 1 时， l 也可以等于 mid + 1
         */
        if (nums[mid] > nums[mid + 1]) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

var findPeakElement = function (nums) {
    let l = 0,
        r = nums.length - 1
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        /**
         * mid < mid + 1 时， l = mid + 1
         * 否则 mid >= mid + 1 时，mid > mid + 1, r = mid; mid = mid + 1， r 也可以等于 mid
         */
        if (nums[mid] < nums[mid + 1]) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

与旋转数组不一样，这道题从左往右，从右往左都可以得到极大值，所以 mid 和左右比都 ok。

lc.240 搜索二维矩阵 II

与 lc.74 不同的是，上一行的尾不再大于下一行的首了。最直观的做法就是对每一行做二分。

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    for (let i = 0; i < matrix.length; i++) {
        const row = matrix[i]
        let l = 0,
            r = row.length
        while (l < r) {
            const mid = l + ((r - l) >> 1)
            if (row[mid] === target) {
                return true
            } else if (row[mid] < target) {
                l = mid + 1
            } else {
                r = mid
            }
        }
    }
    return false
}

这样做的时间复杂度是 O(mlogn)，管解给了更优的方案 Z 字形查找，看了一下就是从右上角进行搜索，根据条件更新坐标 ++y 或 –x。

lc.410 分割数组的最大值 hard

这道题的常规做法是动态规划，能用到二分我是属实没有想到。。。

这道题确实有难度，直接看官解吧，用的是二分+贪心

lc.658 找到 k 个最接近的元素

var findClosestElements = function (arr, k, x) {
    // 先找到 x 的位置 i，再从 i 往左右两边拓展 [p..q] 直到 q - p + 1 === k
    let l = 0,
        r = arr.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (arr[mid] < x) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    /**
     * 关键点，此时 l == r，且 [r..] 都 **大于等于** x; [..r-1] 都小于 x
     *
     * 如过没有 l = r - 1 这一步，那么 [...l] 也都是小于等于 x 的，就丧失了二段性，
     *          当 leftAbs === rightAbs 时，就分不清到底是该 l-- 还是 r++
     *
     * 有了 l == r - 1，则就能保证 [...l] 一定是小于 x 的，也就有了 (l..r] 的可行解区间，
     *          当 leftAbs === rightAbs 时，应该 l--
     */
    l = r - 1
    while (r - l <= k) {
        const leftAbs = x - arr[l]
        const rightAbs = arr[r] - x
        /** 同时需要考虑x不在数组索引内的情况 */
        if (l < 0) {
            r++
        } else if (r > arr.length - 1) {
            l--
        } else if (leftAbs <= rightAbs) {
            l--
        } else {
            r++
        }
    }
    return arr.slice(l + 1, r)
}

再一次加深可行解区间的理解 🐶

lc.793 阶乘函数后 K 个零 hard

数学题，不看答案是真不会啊~

lc.852 山脉数组的峰顶索引

/**
 * @param {number[]} arr
 * @return {number}
 */
var peakIndexInMountainArray = function (arr) {
    let l = 0,
        r = arr.length - 1
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (arr[mid] < arr[mid + 1]) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

就问你这和 lc.162 有啥区别吗。。。

lc.875 爱吃香蕉的珂珂

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, h) {
    // 寻找 k，根据题意 k 的最小值为 1， 最大值为 piles 里的最大值
    let max = 0
    for (const num of piles) {
        max = num > max ? num : max
    }
    let l = 1,
        r = max
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (getHourWhenSpeedIsMid(piles, mid) > h) {
            l = mid + 1
        } else {
            r = mid // 又去收缩右边界了~
        }
    }
    return l
}
function getHourWhenSpeedIsMid(piles, speed) {
    let hours = 0
    for (const num of piles) {
        hours += Math.ceil(num / speed)
    }
    return hours
}

lc.1011 在 D 天内送达包裹的能力

与 lc.875 几乎一模一样

var shipWithinDays = function (weights, days) {
    // 根据题意，最低运载能力的最小值为 weights 的最大值，最大运载能力为 weights 的和
    let l = Math.max(...weights),
        r = weights.reduce((a, b) => a + b)
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (getDays(weights, mid) > days) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}
function getDays(weights, mid) {
    let days = 1
    let count = 0
    for (const weight of weights) {
        count += weight
        if (count > mid) {
            days++
            count = weight
        }
    }
    return days
}

lc.1201 丑数 III

这题也是没点数学知识是真的不会啊 😭 本题答案是我拷贝的，算是开了眼界了

[1..i] 中能被数字 a 整除的数字个数为 i / a
容斥原理：[1..i]中能被 a 或 b 或 c 整除的数的个数 = i/a−i/b−i/c−i/ab−i/bc−i/ac+i/abc。其中 i/ab 代表能被 a 和 b 整除的数，其他同理。

/**
 * @param {number} n
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var nthUglyNumber = function (n, a, b, c) {
    const ab = lcm(a, b)
    const ac = lcm(a, c)
    const bc = lcm(b, c)
    const abc = lcm(ab, c)
    let left = Math.min(a, b, c)
    let right = n * left
    while (left < right) {
        const mid = Math.floor((left + right) / 2)
        const count =
            low(mid, a) +
            low(mid, b) +
            low(mid, c) -
            low(mid, ab) -
            low(mid, ac) -
            low(mid, bc) +
            low(mid, abc)
        if (count >= n) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return right
}
function low(mid, val) {
    return (mid / val) | 0
}
function lcm(a, b) {
    //最小公倍数
    return (a * b) / gcd(a, b)
}
function gcd(a, b) {
    //最大公约数
    return b === 0 ? a : gcd(b, a % b)
}

总结：一旦对循环不变量和可行解区间有了深刻的理解，二分法本身是没有什么难点的，上方的 hard 题，难在了二分与其他逻辑的揉和，比如贪心和数学，所以对于二分本身的东西要贼贼贼熟练的掌握，当成工具一样，在遇到快速查询且能用二分的情况下，能信手拈来，peace！

目录