C++实现二分法详解
2021/7/12 11:09:21
本文主要是介绍C++实现二分法详解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二分法是在一个排好序的序列(数组,链表等)中,不断收缩区间来进行目标值查找的一种算法,下面我们就来探究二分法使用的一些细节,以及常用的场景:
- 寻找一个数;
- 寻找左侧边界;
- 寻找右侧边界。
一、二分法的通用框架
int binarySearch(vector<int>& nums, int target){ int left=0, right=nums.size(); while(left < right) { int mid=(left+right)/2; if(nums[mid] == target){ // 条件一:中间的值与目标值相同 } else if(nums[mid] > target){ // 条件二:中间的值大于目标值 } else if(nums[mid] < target){ // 条件三:中间的值小于目标值 } } return -1; }
首先,我们先来分析一下右边界 right
的初始值:
- 当
right=nums.size()
时,初始化的区间就变成了 [0,right−1][0,right−1],即 [0,right)[0,right); - 当
right=nums.size()-1
时,初始化的区间就变成了 [0,right][0,right]。
在第一种情况下,当 nums[mid] > target
时,需要将区间向左收缩,即 right=mid
。这个做法的逻辑是:既然 mid
位置处大于 target
,而查找区间又是 “左闭右开”,因此当 right=mid
时,新的查找区间变成了 [0,mid)[0,mid),这样才不会漏掉值。同理,当 nums[mid] < target
时,需要将区间向右收缩,即 left = mid+1
,因为在 "左闭右开" 的区间下,新的查找区间变成 [mid+1,right)[mid+1,right) 才不会漏掉值。当目标值不在序列中时,需要将 while
的条件写成 while(left < right)
而不是写成 while(left<=right)
,这样会引起数组越界。
第二种情况的分析类似,这里只给出结论:
- 当
nums[mid] > target
时,需要将区间向左收缩,即right=mid-1
; - 当
nums[mid] < target
时,需要将区间向右收缩,即left = mid+1
; - 当目标值不在序列中时,需要将
while
的条件写成while(left<=right)
二、二分法查找目标值
在序列中查找一个数,如果存在则返回数的索引,如果不存在则返回 -1
。为了方便分析,我们就只用第一种情况进行说明:
int binarySearch(vector<int>& nums, int target){ int left=0, right=nums.size(); while(left < right) { int mid=(left+right)/2; if(nums[mid] == target){ return mid; // 查询到目标值,直接返回目标值的位置 } else if(nums[mid] > target){ right = mid; // 中间的值大于目标值,向左收缩区间 } else if(nums[mid] < target){ left = mid+1;// 中间的值小于目标值,向右收缩区间 } } return -1; // 当没有找到,直接返回-1 }
三、二分法查找目标值的左右边界
上述代码只能从序列中查找一个目标值并返回位置,当一个序列中目标值不止一个时,我们需要找到目标值最左边的位置和最右边的位置,这时候二分法需要进行改写:
// 查找目标值的左边界 int binarySearch(vector<int>& nums, int target){ int left=0, right=nums.size(); while(left < right) { int mid=(left+right)/2; if(nums[mid] == target){ right = mid; // 查询到目标值不进行返回,而是收缩区间继续查找 } else if(nums[mid] > target){ right = mid; // 中间的值大于目标值,向左收缩区间 } else if(nums[mid] < target){ left = mid+1;// 中间的值小于目标值,向右收缩区间 } } return left; }
根据上述代码,可以发现如果查找目标值的左边界,在满足 nums[mid] == target
时,需要缩小搜索区间的上界 right
,在区间 [left,mid][left,mid] 中继续搜索,直到搜索完毕 left==right
。此时 left=right=左边界
。
查找右边界的做法与左边界类似:
// 查找目标值的左边界 int binarySearch(vector<int>& nums, int target){ int left=0, right=nums.size(); while(left < right) { int mid=(left+right)/2; if(nums[mid] == target){ left = mid+1; // 查询到目标值不进行返回,而是收缩区间继续查找 } else if(nums[mid] > target){ right = mid; // 中间的值大于目标值,向左收缩区间 } else if(nums[mid] < target){ left = mid+1;// 中间的值小于目标值,向右收缩区间 } } return left-1; }
注意这里的判断条件改成了当 nums[mid] == target
时,left = mid+1
。因为搜索的区间为 "左闭右开",所以在寻找左边界时可令 right=mid
,在寻找右边界时必须另 left=mid+1
,不然程序会一直停在循环里面而无法跳出循环。
这篇关于C++实现二分法详解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解