二分——力扣篇
创始人
2024-06-01 23:11:23
0次

二分——力扣篇

    • 搜索旋转排序数组
    • 搜索旋转排序数组II
    • 寻找旋转排序数组中的最小值
    • 寻找旋转排序数组中的最小值II

搜索旋转排序数组

在这里插入图片描述

在这里插入图片描述
定理一:只有在顺序区间内才可以通过区间两端的数值判断target是否在其中。

定理二:判断顺序区间还是乱序区间,只需要对比 left 和 right 是否是顺序对即可,left <= right,顺序区间,否则乱序区间。

通过不断的用Mid二分,根据定理二,将整个数组划分成顺序区间和乱序区间,然后利用定理一判断target是否在顺序区间,如果在顺序区间,下次循环就直接取顺序区间,如果不在,那么下次循环就取乱序区间。

  • 注意点一:整体二分前,必须对区间长度进行特判,比如二分之前,如果整个序列长度为1,按我这种二分方式l根本不可能进入二分。
  • 注意点二:判断是否为顺序区间,只需比较该区间左右端点的大小,错误想法是以为不会有重复的元素,所以只需要判断是否左下标对应的元素严格小于右下标对应的元素 ,其实不然,涉及区间必须对区间长度进行特判,比如二分之前,如果整个序列长度为1,按我这种二分方式l根本不可能进入二分。回到判断是否为顺序区间,如果区间长度为1或者2,l的值和mid的值是相等的,指向的自然是同一元素,会是相等的。例子为3 1 找 1。我又想,是不是在整个二分之前特判区间长度为2的情况就OK呢?不对,因为二分就是缩小区间范围的过程,并不一定开局就是target在仅有的两个元素之间,很有可能一直二分直到缩小到区间长度为2
    3、按照这套二分模板,
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;
}

不断缩小区间范围只能遵循一种规律那就是由int mid = l + r >> 1;决定的从小到大找和l = mid + 1; (一定是匹配出现的),或者是由int mid = l + r+1 >> 1;决定的从大到小找和l = mid ; 这里

if(target>=nums[mid]&&target<=nums[r]){if(nums[mid] == target) return mid;else l=mid+1;	
}

如果此时不提前判断mid及时返回mid,那么l应当取的值是l=mid,显然不对(记住死循环解释) OK,提前判断mid,ac啦

class Solution {
public:int search(vector& nums, int target) {int n=nums.size();if(n==0)return -1;if(n==1)return nums[0]==target?0:-1;int l=0,r=n-1;while(lint mid=(l+r)>>1;
//		if(nums[mid] == target) return mid;
//     数组旋转过后一定是一段或者两段上升的子段,仍然可以二分
//     但是整体二分[l,mid]不一定恰好处于上升子段之中,可能包含了俩子段各一部分if(nums[l]<=nums[mid]){//不取等号是因为不存在重复元素 [l,mid]恰好处于升序子段if(target>=nums[l]&&target<=nums[mid]){r=mid;	}else l=mid+1;}else{//[l,mid]不完全处于升序子段,好办,[mid+1,r]一定属于if(target>=nums[mid]&&target<=nums[r]){if(nums[mid] == target) return mid;else l=mid+1;	}else r=mid-1;}}return (nums[l] == target)?l:-1;}
};//3 1  
//1 
//-1 其实是1

另一种二分代码

class Solution {
public:int search(vector& nums, int target) {int n=nums.size();if(n==0)return -1;if(n==1)return nums[0]==target?0:-1;
//      if(n==2){
//      	if(target==nums[0])return 0;
//      	else if(target==nums[1])return 1;
//      	else return -1;
//	  }int l=0,r=n-1;while(l<=r){int mid=(l+r)>>1;if(nums[mid] == target) return mid;
//     数组旋转过后一定是一段或者两段上升的子段,仍然可以二分
//     但是整体二分[l,mid]不一定恰好处于上升子段之中,可能包含了俩子段各一部分if(nums[l]//[l,mid]恰好处于升序子段//不取等号是因为不存在重复元素 ,错,要取, 比如 3 1 找1,l就是mid
//      	5 1 2 3 4找1,只要target找的范围缩小到了旋转点+左 或 右转点+左if(target>=nums[l]&&targetr=mid-1;	}else l=mid+1;}else{//[l,mid]不完全处于升序子段,好办,[mid+1,r]一定属于if(target>nums[mid]&&target<=nums[r]){l=mid+1;	}else r=mid-1;}}return -1;}
};

搜索旋转排序数组II

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

10111 和 11101 这种。此种情况下 nums[start] == nums[mid],分不清到底是前面有序还是后面有序,此时 start++ 即可。相当于去掉一个重复的干扰项。

顺带发现,if(nums[mid] == target) return true;用我的二分模板,每次得到mid先判断也无伤大雅,提前发现提前返回而已,主要是注意缩小区间的方式

class Solution {
public:int search(vector& nums, int target) {int n=nums.size();if(n==0)return -1;if(n==1)return nums[0]==target?true:false;int l=0,r=n-1;while(lint mid=(l+r)>>1;if(nums[mid] == target) return true;if (nums[l] == nums[mid] && nums[mid] == nums[r]) {++l;--r;}else if(nums[l]<=nums[mid]){//不取等号是因为不存在重复元素 [l,mid]恰好处于升序子段if(target>=nums[l]&&target<=nums[mid]){r=mid;	}else l=mid+1;}else{//[l,mid]不完全处于升序子段,好办,[mid+1,r]一定属于if(target>=nums[mid]&&target<=nums[r]){if(nums[mid] == target) return true;else l=mid+1;	}else r=mid-1;}}return (nums[l] == target)?true:false;}
};//3 1  
//1 
//-1 其实是1

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

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
三种情况主要就是mid落在的位置不同,需要使区间来到第二段

class Solution {
public:int findMin(vector& nums) {int n=nums.size();int l=0,r=n-1;while(lint mid=l+r>>1;
//经由 1 到 n 次 旋转,两段升序子序列,且第一段大于第二段,最小值一定在第二段if(nums[mid]
//				l=mid;r=mid;}else{
//				r=mid-1;//不对的,记住永远在 第二段 找,lr需要使区间缩小到第二段l=mid+1;}}return nums[l];}
};

寻找旋转排序数组中的最小值II

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

class Solution {
public:int findMin(vector& nums) {int n=nums.size();int l=0,r=n-1;while(lint mid=l+r>>1;
//经由 1 到 n 次 旋转,两段升序子序列,且第一段大于第二段,最小值一定在第二段if(nums[mid]
//				l=mid;r=mid;}else if(nums[mid]>nums[r]){
//				r=mid-1;//不对的,记住永远在 第二段 找,lr需要使区间缩小到第二段l=mid+1;}else {//if(nums[mid]==nums[r])r--;}}return nums[l];}
};

相关内容

热门资讯

存储芯片巨头的好日子何时结束 ... 摩根士丹利最新报告指出,旧存储芯片行业的前景被低估。曾经因供需失衡而获得高额利润的旧存储芯片现在正处...
国足开场2分钟落后 邵佳一眉头... 点击加载图片直播吧11月17日讯 国足开场2分钟丢球,0-1落后巴林,镜头给到眉头紧锁的邵佳一。国字...
小米:相关内容纯属虚构,警惕虚... 小米旗下微博账号“小米辟谣”于11月17日发布声明,指出近期有不法分子冒充“小米汽车”发送诈骗短信,...
最差密码榜单公布 123456... 网络安全公司 NordPass 发布了《2026 年最常用密码 Top 200》报告,指出“1234...
2岁孩子生命最后11天依然努力... 25岁的妈妈将患有罕见病的儿子兜兜送进了长沙的“雏菊之家”安宁病房。她陪伴儿子度过了最后11天,并每...
13岁少年被控杀害5岁男童案 ... 一名13岁少年因妹妹被邻居5岁男童撒沙而心生怨恨,将男童带至桥上推下水致其溺亡。此案引起了媒体的广泛...
全球顶尖科学家加速回流中国 风... 全球顶尖科学家纷纷选择离开美国,转向中国任职。2026年初,莱斯大学90后斯隆奖得主汪淏田全职加盟同...
APEC工商领导人峰会今天聚焦... 11月17日,来自亚太经合组织21个经济体及英国、法国、德国、瑞士等13个域外经济体的2000多位政...
雷军APEC发言 具身智能潜力... 11月17日,小米CEO雷军在2026年APEC工商领导人峰会上表示,具身智能机器人的潜力超过汽车,...
俄罗斯记者惊呼在深圳谁还用现金... 11月17日,今日俄罗斯国际通讯社记者德米特里·加夫里洛夫在接受采访时分享了他的深圳体验。他提到,刚...
雷军:智能机器人产业潜力超汽车... 11月17日,在2026年亚太经合组织工商领导人峰会上,小米CEO雷军介绍了公司在AI、智能制造和机...
保研举报成风,这不只是“坏人变... 保研举报成风,这不只是“坏人变小了” 制度留操作空间。高校保研季举报成风:这不是学生坏,是制度留了太...
广东01年医护女孩为00年闺蜜... 据河南广播电视台小莉帮忙,广东一位01年的女孩,亲自为自己00年的闺蜜接生。她们的缘分有多深?女孩称...
广东网友为迎接APEC会议周有... 11月14日,2026年APEC领导人会议周新闻中心举办了广东省、深圳市专场中外媒体吹风会。这是20...
动车插座在头顶被吐槽像在打吊瓶... 近日,有网友在社交平台发帖分享自己的乘车经历:乘坐D2928次动车组时,发现车厢内的充电插座安装在顶...
万斯称与特朗普无分歧 一致反对... JD·万斯周一表示,他与总统唐纳德·特朗普在伊朗战争问题上完全一致。此前,他曾将共和党在中期选举中的...
痛风人群这4种饮品要少喝 咖啡... 很多尿酸高、痛风人群都知道啤酒、果汁会升高尿酸,那么有没有什么饮料对尿酸“很友好”,甚至还能降低痛风...
医生辟谣左侧睡根本不伤心:正常... 11月17日,经常朝左睡对心脏的影响引发关注。从解剖学角度看,心脏虽然位于胸腔偏左,但它并非孤零零地...
96岁奶奶扒着车窗含泪送孙女返... 近日,湖南,假期快要结束,孙女准备返程。96岁的奶奶扒着车窗,眼里满是不舍。一句有空常回家看看,戳中...
人民日报:从《持械入宋》火爆看... 有能够让行业内外普遍认可的作品出现,是一种新文艺类型成熟的重要标志。正是因为“家里家外”系列、《盛夏...