侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【算法】二分查找模板与其实际应用

GabrielxD
2022-11-05 / 0 评论 / 0 点赞 / 29 阅读 / 1,437 字 / 正在检测是否收录...

二分查找模板

相等

int binary_search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

左边界

找到等于 x 的元素中最靠左的索引,没有符合要求的索引则返回 -1
等同于下文的:大于等于

int left_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left < nums.size() && nums[left] == target ? left : -1;
}

右边界

找到等于 x 的元素中最靠右的索引,没有符合要求的索引则返回 -1
等同于下文的:小于等于

int right_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] > target) right = mid;
        else left = mid + 1;
    }
    return --left >= 0 && nums[left] == target ? left : -1;
}

小于等于

找到小于等于 x 的元素中最大的索引,没有符合要求的索引则返回 -1

int bsearch_leq(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] > target) right = mid;
        else left = mid + 1;
    }
    return --left >= 0 && nums[left] <= target ? left : -1;
}

大于等于

找到大于等于 x 的元素中最小的索引,没有符合要求的索引则返回 -1

int bsearch_geq(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left < nums.size() && nums[left] >= target ? left : -1;
}

实际应用

什么问题可以运用二分搜索算法技巧?

首先,你要从题目中抽象出一个自变量 x,一个关于 x 的函数 f(x),以及一个目标值 target

同时,x, f(x), target 还要满足以下条件:

1、f(x) 必须是在 x 上的单调函数(单调增单调减都可以)

2、题目是让你计算满足约束条件 f(x) == target 时的 x 的值

上述规则听起来有点抽象,来举个具体的例子:

给你一个升序排列的有序数组 nums 以及一个目标元素 target,请你计算 target 在数组中的索引位置,如果有多个目标元素,返回最小的索引。

这就是「搜索左侧边界」这个基本题型,解法代码之前都写了,但这里面 x, f(x), target 分别是什么呢?

我们可以把数组中元素的索引认为是自变量 x,函数关系 f(x) 就可以这样设定:

// 函数 f(x) 是关于自变量 x 的单调递增函数
// 入参 nums 是不会改变的,所以可以忽略,不算自变量
int f(int x, int[] nums) {
    return nums[x];
}

其实这个函数 f 就是在访问数组 nums,因为题目给我们的数组 nums 是升序排列的,所以函数 f(x) 就是在 x 上单调递增的函数。

最后,题目让我们求什么来着?是不是让我们计算元素 target 的最左侧索引?

是不是就相当于在问我们「满足 f(x) == targetx 的最小值是多少」?

画个图,如下:

img

如果遇到一个算法问题,能够把它抽象成这幅图,就可以对它运用二分搜索算法

算法代码如下:

// 函数 f 是关于自变量 x 的单调递增函数
int f(int x, int[] nums) {
    return nums[x];
}

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (f(mid, nums) == target) {
            // 当找到 target 时,收缩右侧边界
            right = mid;
        } else if (f(mid, nums) < target) {
            left = mid + 1;
        } else if (f(mid, nums) > target) {
            right = mid;
        }
    }
    return left;
}

这段代码把之前的代码微调了一下,把直接访问 nums[mid] 套了一层函数 f,其实就是多此一举,但是,这样能抽象出二分搜索思想在具体算法问题中的框架。

运用二分搜索的套路框架

想要运用二分搜索解决具体的算法问题,可以从以下代码框架着手思考:

// 函数 f 是关于自变量 x 的单调函数
int f(int x) {
    // ...
}

// 主函数,在 f(x) == target 的约束下求 x 的最值
int solution(int[] nums, int target) {
    if (nums.length == 0) return -1;
    // 问自己:自变量 x 的最小值是多少?
    int left = ...;
    // 问自己:自变量 x 的最大值是多少?
    int right = ... + 1;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (f(mid) == target) {
            // 问自己:题目是求左边界还是右边界?
            // ...
        } else if (f(mid) < target) {
            // 问自己:怎么让 f(x) 大一点?
            // ...
        } else if (f(mid) > target) {
            // 问自己:怎么让 f(x) 小一点?
            // ...
        }
    }
    return left;
}

具体来说,想要用二分搜索算法解决问题,分为以下几步:

  1. 确定 x, f(x), target 分别是什么,并写出函数 f 的代码
  2. 找到 x 的取值范围作为二分搜索的搜索区间,初始化 leftright 变量
  3. 根据题目的要求,确定应该使用搜索左侧还是搜索右侧的二分搜索算法,写出解法代码

参考

0

评论区