首页 > 其他分享 >二分搜索套路

二分搜索套路

时间:2024-02-06 16:55:20浏览次数:32  
标签:二分 target nums 套路 mid int 搜索 left

我们前文 我写了首诗,把二分搜索变成了默写题 详细介绍了二分搜索的细节问题,探讨了「搜索一个元素」,「搜索左侧边界」,「搜索右侧边界」这三个情况,教你如何写出正确无 bug 的二分搜索算法。

但是前文总结的二分搜索代码框架仅仅局限于「在有序数组中搜索指定元素」这个基本场景,具体的算法问题没有这么直接,可能你都很难看出这个问题能够用到二分搜索。

所以本文就来总结一套二分搜索算法运用的框架套路,帮你在遇到二分搜索算法相关的实际问题时,能够有条理地思考分析,步步为营,写出答案。

原始的二分搜索代码

二分搜索的原型就是在「有序数组」中搜索一个元素 target,返回该元素对应的索引。

如果该元素不存在,那可以返回一个什么特殊值,这种细节问题只要微调算法实现就可实现。

还有一个重要的问题,如果「有序数组」中存在多个 target 元素,那么这些元素肯定挨在一起,这里就涉及到算法应该返回最左侧的那个 target 元素的索引还是最右侧的那个 target 元素的索引,也就是所谓的「搜索左侧边界」和「搜索右侧边界」,这个也可以通过微调算法的代码来实现。

我们前文 我写了首诗,把二分搜索变成了默写题 详细探讨了上述问题,对这块还不清楚的读者建议复习前文,已经搞清楚基本二分搜索算法的读者可以继续看下去。

在具体的算法问题中,常用到的是「搜索左侧边界」和「搜索右侧边界」这两种场景,很少有让你单独「搜索一个元素」。

因为算法题一般都让你求最值,比如让你求吃香蕉的「最小速度」,让你求轮船的「最低运载能力」,求最值的过程,必然是搜索一个边界的过程,所以后面我们就详细分析一下这两种搜索边界的二分算法代码。

注意,本文我写的都是左闭右开的二分搜索写法,如果你习惯两端都闭的写法,可以自行改写代码。

「搜索左侧边界」的二分搜索算法的具体代码实现如下:

// 搜索左侧边界
int left_bound(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size();

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

「搜索右侧边界」的⼆分搜索算法的具体代码实现如下:
// 搜索右侧边界
int right_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 (nums[mid] == target) {
 // 当找到 target 时,收缩左侧边界
 left = mid + 1;
 } else if (nums[mid] < target) {
 left = mid + 1;
 } else if (nums[mid] > target) {
 right = mid;
 }
 }
 return 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) == target 的 x 的最⼩值是多少」?

画个图,如下:

如果遇到⼀个算法问题,能够把它抽象成这幅图,就可以对它运⽤⼆分搜索算法。
算法代码如下:

int f(int x, int nums[]) {
return nums[x];
}

int left_bound(int nums[], int target) {
int len = sizeof(nums) / sizeof(nums[0]);
if (len == 0) return -1;

int left = 0, right = len;

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 (sizeof(nums) / sizeof(nums[0]) == 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 的取值范围作为⼆分搜索的搜索区间,初始化 left 和 right 变量。

3、根据题⽬的要求,确定应该使⽤搜索左侧还是搜索右侧的⼆分搜索算法,写出解法代码。

下⾯⽤⼏道例题来讲解这个流程。

标签:二分,target,nums,套路,mid,int,搜索,left
From: https://www.cnblogs.com/lulixiu1999/p/18009988

相关文章

  • linux 搜索zip压缩文件内的关键字
    有这样一个场景,一个应用有日志归档,每天新建一个文件夹文件夹里是zip压缩文件             这时候如果程序出现问题,但是不确定是哪一天,需要搜索这些天里的日志文件关键字,这个怎么弄问题比较棘手,经过一番琢磨还是解决了:zgrep'deletefromt_common......
  • 【译】VisualStudio 17.9预览3带来了令人兴奋的代码搜索改变
    随着VisualStudio17.9预览版3的发布,我们为代码搜索(也称为All-In-OneSearch)带来了一些令人兴奋的增强。自从我们上次更新搜索体验以来,我们一直在努力改进体验,并想出增加体验的方法。现在,您可以在解决方案中搜索任何单词或字符串,补充来自代码库的文件和符号结果。现在可以......
  • 【洛谷 P2437】蜜蜂路线 题解(递归+记忆化搜索+高精度)
    蜜蜂路线题目描述一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房开始爬到蜂房,,有多少种爬行路线?(备注:题面有误,右上角应为)输入格式输入的值输出格式爬行有多少种路线样例#1样例输入#1114样例输出#1377提示对于100%的......
  • SharePoint Online 禁用搜索功能
    前言我们在使用SharePointOnline的时候,经常发现搜索的时候,能搜到很多意外出现的文档,有时候是敏感文档,有时候是图片、脚本素材,这样很不友好。其实,我们可以在网站中进行设置,让不该出现的内容不被爬网或者不显示出来。正文首先,文档库是可以设置是否开启搜索......
  • 代码随想录 day41 整数拆分 不同的二叉搜索树
    整数拆分这里的递推式子很不好想一般的想法是dp[i]=max(dp[i],dp[i-j])但是这个式子需要赋值dp[1]=1dp[2]=2dp[3]=3这个不符合dp[i]定义这里递推式子如下dp[i-j]等于拆分成两个或两个以上的数字i*(i-j)就是两个数字拆分不同的二叉搜索树难点依旧是递推式是怎么......
  • 搜索
    搜索小技巧一个搜索要知道如何剪枝,但剪枝是一个难点。在写搜索的时候,我们要想会不会有冗杂的多余的搜索产生,如果有,我们就可以用记忆化搜索/剪枝或者说如果后面的条件可以包含于前面的,那我们就可以用剪枝来处理掉如:给定一个数m,我要在若干个数中,找到一些数,使他的重量最接近我们......
  • 二分
    二分好题A.1.喂养宠物-「基础算法」第3章二分算法强化训练-高效进阶-课程-YbtOJ这是一道简单题。就是我们枚举一下我们选择的\(m\)个兔子,然后求出所有兔子的价值,之后我们排序,从小到大选择。code:#include<bits/stdc++.h>//#defineintlonglongusingnamespace......
  • 二分查找BinarySearch
    二分查找法首先,整个数组必须有序,通常为递增。将数组中间数字与被比较元素比较相等即目标元素为被比较元素中间元素大于目标元素,意味着中间元素右边的所有元素均大于目标元素,排除中间元素小于目标元素,意味着中间元素左边的所有元素均小于目标元素,排除当数组元......
  • 【学习笔记】网络流与二分图初步
    网络流与二分图初步我们约定,对于有向图\(G=(V,E)\),分析复杂度时\(m=|E|,n=|V|\)。在分析时间复杂度时,网络流的实际表现基本都优于其理论上的时间复杂度表现。I概念(1)网络流:在一个有向带权图上(不考虑自环和重边),与最短路类似,我们定义一个源点\(s\)和一个汇点\(t\)......
  • 线段树二分——nc2.4多校_G.新春漫步
    目录问题概述思路分析参考代码做题反思问题概述原题参考G.新春漫步坐标轴上有n个点,初始时每个位置上都有一个坚固程度为a1的障碍物,接下来有m次操作1.将位置p上的障碍物的坚固程度减去x,若减去x后坚固程度小于等于0,则该障碍物消失2.询问一个人从p的位置向右走,最多能走到什么位......