二分查找模板,包括左边界右边界
模板 查找 包括 边界 二分
2023-06-13 09:16:13 时间
一次记住所有情况
二分法最怕的就是边界的处理,一般见到的就是下面三种情况
假设数组是升序的
查找元素
int binary(vector<int> nums, int target){
int n=nums.size();
int l=0, r=n-1;
while(l<=r){
int mid=(l+r)/2;
if(nums[mid]==target) return mid;
else if(nums[mid]>target) r=mid-1;
else l=mid+1;
}
return -1;
}
寻找左边界情况,右边要往左边靠
int binary(vector<int> nums, int target){
int n=nums.size();
int l=0, r=n-1;
while(l<=r){
int mid=(l+r)/2;
if(nums[mid]<target) l=mid+1;;
else r=mid-1;
}
if(l>=n || nums[l]!=target) return -1;
return l;
}
寻找右边界情况,左边要往右边靠
int binary(vector<int> nums, int target){
int n=nums.size();
int l=0, r=n-1;
while(l<=r){
int mid=(l+r)/2;
if(nums[mid]>target) r=mid-1;;
else l=mid+1;
}
if(r<0 || nums[r]!=target) return -1;
return r;
}
相关文章
- 二分查找不同模板分析与比较
- T11 Origin绘图模板
- 请描述django模板中标签的作用?_抽奖券模板
- 5种前端代码共享方案:npm包、git submodules、脚手架模板、复制、UMD或模块联邦
- thymeleaf模板注入学习与研究--查找与防御
- WordPress主题制作(二):模板和模板文件
- 【算法】二分法 ② ( 排序数组中查找目标值 | 二分法的经典写法 | 在排序数组中查找元素的最后一个位置 | 二分法的通用模板 )
- 下载模板,上传EXCEL详解编程语言
- 用搜狗输入法心情模板 快速获取朋友圈运动盛会加油文案!
- 「自制」Linux PPT模板:简约风格,打造专业演示(linuxppt模板)
- 不用模板,只用ASP+FSO生成静态HTML页的一个方法
- phpHttp_Template_IT类库进行模板替换