算法系列之新思路搞定二分法的边界问题

算法系列之新思路搞定二分法的边界问题

引用

CSDN

1.

https://m.blog.csdn.net/cherry__yu/article/details/137148144

二分查找算法虽然在学习阶段反复被提及，但在实际编写时，边界条件、循环条件等细节问题常常让人困扰。本文将介绍一种新的思路——"蓝红区域思想"，帮助读者更好地理解和解决二分查找中的边界问题。

传统二分查找回顾

让我们先回顾一下传统的二分查找实现：

var searchInsert = function(nums, target) {
    const len = nums.length;
    let left = 0;
    let right = len - 1;
    while(left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            return mid;
        }
        if (nums[mid] > target) {
            right = mid - 1;
            continue;
        }
        if (nums[mid] < target) {
            left = mid + 1;
            continue;
        }
    }
    return left;
};

蓝红区域思想

这种方法来自于Bilibili上的一个视频（BV1d54y1q7k7），通过实践发现非常实用。

我们可以将数组想象成一个模型，其中前面的区域是满足某种条件的"蓝色区域"，后面的区域是"红色区域"。初始时，数组没有颜色，我们的目标是找到蓝红区域的边界位置。

实现步骤如下：

1. 初始化两个指针 l 和 r，分别指向蓝色区域和红色区域的边界外（即 -1 和 length）。
2. 通过二分查找，使两个指针快速向蓝红边界逼近，直到 l + 1 = r。
3. 根据具体问题和区域条件定义，决定返回 l 还是 r。

代码模板如下：

l = -1, r = N
while l + 1 !== r
    m = Math.floor((l + r) / 2)
    if isBlue(m)
        l = m
    else
        r = m
return l or r

解题步骤

拿到题目后，我们需要完成以下步骤：

• 建模：划分蓝红区域，确定 isBlue() 函数。
• 确定返回 l 还是 r。
• 套用算法模板。
• 进行一些额外处理（如果需要）。

实例分析

让我们通过两道LeetCode题目来具体说明这种方法的应用。

题目1：二分查找

题目要求：在一个升序数组中查找目标值，如果找到则返回其索引，否则返回 -1。

示例：

• 输入: nums = [-1,0,3,5,9,12], target = 9

• 输出: 4

• 解释: 9 出现在 nums 中并且下标为 4

• 输入: nums = [-1,0,3,5,9,12], target = 2

• 输出: -1

• 解释: 2 不存在 nums 中因此返回 -1

思路：将蓝色区域定义为小于目标值的区域，这样最后划分出的分界点处，红色区域指针指向的就应该是目标值。如果不是的话，说明目标值不存在。

function search(nums: number[], target: number): number {
    let l = -1, r = nums.length;
    while (l + 1 < r) {
        let mid = Math.floor((l + r) / 2); 
        if (nums[mid] < target) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return nums[r] === target ? r : -1;
};

题目2：搜索插入位置

题目要求：在一个排序数组中查找目标值，如果找到则返回其索引；如果未找到，则返回目标值应该插入的位置，以保持数组的升序。

思路：与上一题类似，蓝色区域仍然是小于目标值的区域。这样最后划分出的分界点处，红色区域指针指向的就应该是目标值或插入位置。

var searchInsert = function(nums, target) {
    let l = -1, r = nums.length;
    while (l + 1 < r) {
        mid = Math.floor((l + r) / 2);
        if (nums[mid] < target) {
            l = mid;
            continue;
        }
        r = mid;
    }
    return r;
};

通过这两个例子可以看出，"蓝红区域思想"在处理二分查找问题时具有很强的通用性和灵活性，只需要根据具体问题微调返回值处理即可。