【C++例题 / 训练】二分算法(模板 例题)
引言
二分也就是二分查找,又叫折半查找。这种算法正如其名,每一次都要分一半。
二分算法可以分为二分查找和二分答案。
以在一个升序数组中查找一个数为例,每次考察数组当前部分的中间元素,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果中间元素大于所查找的值同理,只需到左侧查找
二分法的使用条件
二分法是适用于解决具有“二段性”(单调性)的问题的方法,通常表现为求解满足某一条件的最大值或者最小值
- 上下界确定。 我们可以通过上下界的折半来优化查找。
- 二段性: 对某一范围内的数据,存在一个临界点,使得临界点某一侧的所有数据都满足某一性质,另一侧的所有数据都不满足这一性质,就称这一范围内的数据具有二段性。
二段性包括单调性,即区间内有序,这样二分出来的结果是严格大于或者小于或等于target的。
但是,二段性也体现在非单调性上,也称为局部有序,可以参考 162. 寻找峰值 和 33. 搜索旋转排序数组。由这些题我们可以得知,二分法的奥义(本质)不在于单调性,而是二段性。也就是我们能对整体无序但局部有序的序列进行二分法。
二分的前提条件
1、答案在一个区间内(一般情况下,区间会很大,暴力超时)
3、该区间对题目具有单调性,即:在区间中的值越大或越小,题目中的某个量对应增加或减少。
4、若有多个答案满足题意,则这些答案具有如下特点:若答案 x 满足,则答案范围内小于 x 或大于 x 的答案均满足。
模板
🥑1 朴素版
while (l <= r)
{int mid = (r - l) / 2 + l; //防止溢出,和mid = (r - l + 1) / 2 + l;等价if (...) l = mid + 1;else if (...) r = mid - 1;else return ...;
}
🍉2 求大于等于目标的最小值(查找区间左端点)
while (l < r) //区间不为空
{int mid = ((r - l) >> 1) + l;if (...) l = mid + 1; else r = mid;
}
🥝3 求小于等于目标的最大值(查找区间右端点)
while (l < r)
{// 当l,r相邻时,会l=mid,<r,死循环,模板1不影响,因为l=mid+1=r int mid = ((r - l + 1) >> 1) + l;if (...) l = mid;else r = mid - 1;
例题
1. 二分查找
class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while (l <= r){//int mid = (r - l) / 2 + l; //朴素版本下 两个都行int mid = (r - l + 1) / 2 + l;if (nums[mid] == target) return mid;else if (nums[mid] > target) r = mid - 1;else l = mid + 1;}return -1;}
};
2. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if (nums.size() == 0) return { -1,-1 };int begin = 0;// 1. 二分左端点int l = 0, r = nums.size() - 1;while (l < r) //区间不为空{int mid = ((r - l) >> 1) + l;if (nums[mid] < target)l = mid + 1;else r = mid;}// 判断是否有结果if (nums[l] != target) return { -1,-1 };else begin = l; //标记左端点l = 0, r = nums.size() - 1;while (l < r) //区间不为空{int mid = ((r - l + 1) >> 1) + l;if (nums[mid] > target) r = mid - 1;else l = mid;}return { begin, r};}
};
3. x 的平方根
class Solution {
public:int mySqrt(int x) {if (x < 1) return 0;int l = 1, r = x;while (l < r) //精度保证{long long mid = (r - l + 1) / 2 + l; //防止溢出if (mid * mid <= x) l = mid;else r = mid - 1;}return l;}
};
4. 搜索插入位置
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int l = 0, r = nums.size();while (l < r){int mid = (r - l) / 2 + l;if (nums[mid] < target) l = mid + 1;else r = mid;}return l;}
};
5. 山脉数组的峰顶索引
思路:
该题仍具有二段性,左边递增,右边递减,用二分查找算法,
当前山峰高于左边山峰,区间往右缩小,否则往左缩小
注:封顶的左边区间,一定是递增的,因此套用模板三即可,找最右端点
class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int l = 1, r = arr.size() - 2;while (l < r){int mid = l + (r - l + 1) / 2;if (arr[mid] > arr[mid - 1]) l = mid;else r = mid - 1;}return r;}
};
6、寻找峰值
思路:
该题相比于上题,该题有多个峰值存在,故在两个封顶之间的区间内,从左到右一定递增,故套用模板二,找区间左端点即可。
class Solution {
public:int findPeakElement(vector<int>& nums) {int l = 0, r = nums.size() - 1;while (l < r) // 左边如果不大于右边,则{int mid = (r - l) / 2 + l;if (nums[mid] > nums[mid + 1]) r = mid ; else l = mid + 1;}return l;}
};
7. 寻找旋转排序数组中的最小值
思路:
class Solution {
public:int findMin(vector<int>& nums) {int l = 0, r = nums.size() - 1;int x = nums[r];while (l < r){int mid = (r - l) / 2 + l;if (nums[mid] <= x) r = mid;else l = mid + 1;}return nums[l];}
};
8. 点名
思路:
按照缺失的数分为左右两个区间。
左边,nums[i] == i (left = i + 1)
右边 nums[i] > i. (right = i)
注:当缺失的数是最后一个数,需要做下特殊判断,因此r 从 n 开始
class Solution {
public:int takeAttendance(vector<int>& records) {int l = 0, r = records.size();while (l < r){int mid = (r - l) / 2 + l;if (records[mid] == mid) l = mid + 1;else r = mid;}return l;}
};