知识点补充:
1.二分的作用
二分是用来查找某个【目标】的。
2.二分的前提条件
1.一般的,大家通常认为具有单调性(升序,降序)的序列才可以使用二分,但这种场景可以使用二分并不是因为它有单调性,而是它具有二段性。
2.二段性:在序列中任取一个点,该点将序列分成两个部分,通过该点的【状态】可以判断出【目标】在那个部分。
3.二分的高度抽象化模板
左边的模板叫左端点模板,右边的模板叫右端点模板
八道练习题
1.二分查找
. - 力扣(LeetCode)
算法思想:
任取一个点,该点有三种状态。
1.该点比【目标】小---->目标在该点右边
2.该点比【目标】大---->目标在该点左边
3.该点和目标相等---->得到结果,退出
代码实现:
class Solution {
public:int search(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while(l <= r) {int m = l + (r - l) / 2;if(nums[m] < target) l = m + 1;else if(nums[m] > target) r = m - 1;else return m; }return -1;}
};
2.在排序数组中查找第一个和最后一个位置
. - 力扣(LeetCode)
算法思想:
先使用左端点模板找左端点
任取一个点(X),他将序列分成两个部分,该点有两个状态
1.该点小于【目标】
序列被分为【begin,X】,(X,end】(start指第一个元素,end指最后一个元素)
此时走向第二个区间
2.该点大于等于【目标】
序列被分为【begin,X】,(X,end】
此时走向第一个区间
人话:如果该点小了,那么该点和该点左边的元素都不需要了
如果该店大了或相等,那么该点右边的元素都不需要了,但该点不能排除
注意:取中间值的时候要往左取一点
举例:1,2,3,4
这里有四个数,中间值取2
取法可见上面的模板
再使用右端点模板找右端点
任取一个点(X),他将序列分成两个部分,该点有两个状态
1.该点小于等于【目标】
序列被分为【begin,X),【X,end】(start指第一个元素,end指最后一个元素)
此时走向第二个区间
2.该点大于【目标】
序列被分为【begin,X),【X,end】
此时走向第一个区间
人话:如果该点小了或相等,那么该点左边的元素都不需要了,但该点不能排除
如果该店大了,那么该点和该点右边的元素都不需要了
4.取中间值的时候要往左取一点
举例:1,2,3,4
这里有四个数,中间值取3
取法可见上面的模板
特殊情况:
数组中可能没有元素。
代码实现:
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0) return {-1, -1};int ansl, ansr;int l = 0, r = nums.size() - 1;while(l < r) {long long m = l + (r - l) / 2;if(nums[m] < target) l = m + 1;else r = m;}if(nums[l] != target) return {-1, -1};ansl = l, l = 0, r = nums.size() - 1;while(l < r) {long long m = l + (r - l + 1) / 2;if(nums[m] <= target) l = m;else r = m - 1;}ansr = l;return {ansl, ansr};}
};
3.搜索插入位置
. - 力扣(LeetCode)
算法思想
问题转换:找大于等于target的最左端点,直接套用左端点模板。
特殊情况:
序列中的所有值可能都比target小
代码实现:
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;if(target > nums[r]) return r + 1;while(l < r) {int m = l + (r - l) / 2;if(nums[m] < target) l = m + 1;else r = m;}return l;}
};
4.山峰数组的峰顶索引
. - 力扣(LeetCode)
算法思想:
该序列可分为两部分,左边的部分是递增,右边的部分(包括山峰)是递减。
山峰就是递减区间的左端点,直接套用左端点模板。
代码实现:
class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int l = 0, r = arr.size() - 1;while(l < r) {int m = l + (r - l) / 2;if(arr[m] < arr[m + 1]) l = m + 1;else r = m;}return l;}
};
5.寻找峰值
. - 力扣(LeetCode)
注意:这里也将山峰看成递减的
任取一个点,他将序列分成两个部分,该点有两个状态
1.该点递增
序列被分为【begin,X】,(X,end】
走向第二个区间(该区间内一定有一个山峰)
2.该点递减
序列被分为【begin,X】,(X,end】
走向第一个区间(该区间内一定有一个山峰)
很明显,这就是左端点模板。
代码实现:
class Solution {
public:int findPeakElement(vector<int>& nums) {int l = 0, r = nums.size() - 1;while(l < r) {int m = l + (r - l) / 2;if(nums[m] < nums[m + 1]) l = m + 1;else r = m;}return l;}
};
6.X的平方根
. - 力扣(LeetCode)
算法思想:
该序列分为两个部分
左边的部分中,所有元素的平方都小于等于target
右边的部分中,所有元素的平方都大于target
问题转化:找左边部分的最右端点,直接套用右端点模板
代码思想:
class Solution {
public:int mySqrt(int x) {long long l = 0, r = x;while(l < r) {long long m = l + (r - l + 1) / 2;if(m * m <= x) l = m;else if(m * m > x) r = m - 1;}return l;}
};
7.寻找旋转排序数组中的最小值
. - 力扣(LeetCode)
算法思想:
特殊情况:
旋转后该序列可能还是单调递增,要注意细节,但本方法恰好解决了这种场景
代码实现:
class Solution {
public:int findMin(vector<int>& nums) {int key = nums.back();int l = 0, r = nums.size() - 1;while(l < r) {int m = l + (r - l) / 2;if(nums[m] <= key) r = m;else l = m + 1;} return nums[l];}
};
8.点名
. - 力扣(LeetCode)
算法思想
该序列分为两部分
左边的部分:i == records[i]
右边的部分:i != records[i]
问题转换:找右边部分的最左端点,直接套用左端点模型
特殊情况:
可能缺席的是最后一个同学,要特殊处理
代码实现:
class Solution {
public:int takeAttendance(vector<int>& records) {int l = 0, r = records.size() - 1;if(r == records[r]) return r + 1;while(l < r) {int m = l + (r - l) / 2;if(m == records[m]) l = m + 1;else r = m;} return l;}
};