二分算法
一、第一种二分(easy)
例题一：力扣704. 二分查找 - 力扣（LeetCode）
方法：
1.暴力
循环遍历，时间复杂度为O(n)，代码太简单就省略了也不建议用这种方法
2.二分算法(重点)时间复杂度O(logn)
解法思路:
如果利用暴力那么这道题有一个很重要的条件没有用,那就是有序,如果选取某个点为分界点,那么就可以把该区域划分为两个部分,即二段性这就是可以利用二分法解题的原理!
-
a.一定包含target的区间
-
b.一定没有target的区间
这样可以快速舍弃一段区间的数值,提高效率,所以一开始就要选取某个点为分界点,而这个点往往是中点(当然三分点…也是可以的,但是根据数学知识二分是效果最好的),这也就是二分名字的来源
细节:(重难点)
- 最重要的就是分类讨论好二分
- 什么是区间不变量?比如:区间取左闭右闭的话,那么每次区间二分范围都是新区间的左闭右闭 ,后面做判断时要一直基于这个左闭右闭的区间.根据此判断while循环的控制条件要不要带=号,还有移动左右指针时候要不要跨过mid.
- 每次取中点时要防止溢出,所以一般不用mid=(l+r)/2,而是利用左指针移动了区间的一步算mid,即mid=l+(r-l)/2
代码版本一(左闭右闭)
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) { //比如剩一个元素[1,1]由于闭区间可以取=号
int mid = (r - l) / 2 + l;
if (nums[mid] < target)
l = mid + 1; //mid一定不满足条件,所以l移动直接跨过
else if (nums[mid] > target)
r = mid - 1; //mid一定不满足条件,所以r移动直接跨过
else
return mid;
}
return -1;
}
};
代码版本二(左闭右开)
class Solution {
public:
int search(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 if (nums[mid] > target)
r = mid;
else
return mid;
}
return -1;
}
};
补充：
取中点操作一般有两种 mid = l + (r - l ) / 2 和 mid = l + (r - l + 1) / 2 ，区别在于偶数个时，前者取中间偏左的那个数值，而后者取中间偏右的数值，对于本题两者都可以，所以不再此强调。
二、寻找左侧边界的二分查找和寻找右侧边界的二分查找
例题二力扣34. 在排序数组中查找元素的第一个和最后一个位置
方法：
1.暴力
循环遍历，时间复杂度为O(n)，代码太简单就省略了也不建议用这种方法
2.二分算法(重点)时间复杂度O(logn)
解法思路：(以下只显示左右都闭区间的写法)
根据mid的值可以将数组划分为两部分，即二段性
例如：输入：[1,2,3,3,3,4]，target = 3
输出：[2,4]
首先定义左右指针：l = 0,r = nums.size()-1;
-
寻找左边界时候：输入：[ 1,2 ‾ \underline{\text{1,2}} 1,2， 3,3,3,4 ‾ \underline{\text{3,3,3,4}} 3,3,3,4]，根据下划线，将区间分为两部分，左边小于target，右边大于等于tagret.如果mid在左半区间,就得移动左指针,一定是l = mid + 1,因为左端点只在右半区间出现,如果mid在右半区间则移动右指针,是r = mid
详细叙述: 用 resLeft 表示左边界；
我们注意到以左边界划分的两个区间的特点：
- 左边区间 [l, resLeft - 1] 都是小于 x 的；
- 右边区间（包括左边界） [resLeft, r] 都是大于等于 x 的；
- 因此，关于 mid 的落点，我们可以分为下面两种情况：
- 当我们的 mid 落在 [l, resLeft - 1] 区间的时候，也就是 arr[mid] <target 。说明 [l, mid] 都是可以舍去的，此时更新 l 到 mid + 1 的位置，继续在 [mid + 1, r] 上寻找左边界；
- 当 mid 落在 [resLeft， r] 的区间的时候，也就是 arr[mid] >= target 。说明 [mid + 1, r] （因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时更新 r 到 mid 的位置，继续在 [l, mid] 上寻找左边界.
-
寻找右边界时候:输入：[ 1,2,3,3,3 ‾ \underline{\text{1,2,3,3,3}} 1,2,3,3,3， 4 ‾ \underline{\text{4}} 4],根据下划线,将区间分为两部分,左边小于等于target,右边大于target,如果mid在左半区间就得移动左指针,l = mid,因为左区间包含右端点,如果mid在右半区间则移动右指针,为r = mid - 1,因为右半区间没有右端点,(根据闭区间原则)
详细叙述: 用 resRight 表示右边界；
我们注意到以左边界划分的两个区间的特点:
-
我们注意到右边界的特点：
-
左边区间（包括右边界） [l, resRight] 都是小于等于 x 的；
-
右边区间 [resRight+ 1, r] 都是大于 x 的；
-
因此，关于 mid 的落点，我们可以分为下面两种情况：
-
当我们的 mid 落在 [l, resRight] 区间的时候，说明 [l, mid - 1]（ mid 不可以舍去，因为有可能是最终结果）都是可以舍去的，此时更新 l 到 mid 的位置；
-
当 mid 落在 [resRight+ 1, r] 的区间的时候，说明 [mid, r] 内的元素是可以舍去的，此时更新 r 到 mid - 1 的位置.
-
细节(重点)(均为闭区间的写法细节)：
- while循环控制条件:无论寻找左侧边界还是右侧边界,都只能是while(l < r),因为l = r的时候就是最终结果无需判断,而且一旦相等就会死循环.
- 求中点的方式: 寻找左边界时候的求中点方式为 mid = l + (r - l ) / 2 ,寻找右边界的时候求中点方式为 mid = l + (r - l + 1) / 2 ,否则就会死循环.
代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// 处理nums为空的情况
if (nums.size() == 0)
return {-1, -1};
// 查找区间左端点
int begin = -1;
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
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 = l + (r - l + 1) / 2;
if (nums[mid] <= target)
l = mid;
else
r = mid - 1;
}
return {begin, r};
}
};
模板:
- 寻找左边界:
while(l < r)
{
int mid = l + (r - l) / 2;
if(...) l = mid + 1;
else r = mid;
}
- 寻找右边界
while(l < r)
{
int mid = l + (r - l + 1) / 2;
if(...) l = mid;
else r = mid - 1;
}
记忆方法:
- while循环要牢记
- 求中点mid时候,下面 - 1,则上面 + 1，即只有 right - 1 的情况下，才会向上取整（也就是 +1 取中间数）
- 分类讨论if那块时候看二段性如何划分的
习题
1.力扣69. x 的平方根
二分法：（利用查找右侧边界的二分模板(不用太在意用哪个模板)）
算法思路：
由题可知，想求x的平方根就要：求x之前数字的平方与x比较，当然可以优化到求x/2之前的数字的平方，因为之前的数字都是有序的满足二段性，可以使用二分算法，就比如求8的平方根，可以把从1到4的数据划分为两个部分，1，2为一组（平方小于等于x），3，4为另一组（平方大于x），所以当mid在左半区间时候，就得移动l指针到mid的位置（mid可能为结果），当mid落到右半区间的时候，移动r指针到mid-1。
代码cpp
class Solution {
public:
int mySqrt(int x) {
if (x < 1)
return 0; //小于0的情况直接特殊处理
int l = 1, r = x / 2;
while (l < r) {
long long mid = l + (r - l + 1) / 2; //防止溢出
if (mid * mid <= x)
l = mid;
else
r = mid - 1;
}
return l;
}
};
2.力扣367. 有效的完全平方数
二分法：（最简单的模板（第一种二分））
代码cpp
class Solution {
public:
bool isPerfectSquare(int num) {
int l = 1, r = num;
while (l <= r) {
long long mid = l + (r - l) / 2;
if (mid * mid == num)
return true;
else if (mid * mid < num)
l = mid + 1;
else
r = mid - 1;
}
return false;
}
};
tips：如果想优化，可以利用(n+1)2-n2=2n+1，r=num/2……方法，但注意细节
3.力扣852. 山脉数组的峰顶索引
二分法:
从该题可以看出，只要满足二段性的题目数据，都可以使用二分算法，而非只有有序才可以。
代码cpp
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int l = 0, r = arr.size() - 1;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (arr[mid - 1] < arr[mid])
l = mid;
else
r = mid - 1;
}
return l;
}
};
4.力扣162. 寻找峰值
二分法：
你可以假设
nums[-1] = nums[n] = -∞。
根据某点 i 位置的值 arr[i] 与 arr[i+1] 的大小的比较可以将区间划分为两个部分,如果 arr[i] < arr[i+1] ，那么右半区间一定存在峰值，所以接下来去右半区间查找，如果 arr[i] > arr[i+1] ，那么左半区间一定有峰值，去左半区间查找,这就是本题的二段性。
代码cpp版本一
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (nums[mid] < nums[mid + 1])
l = mid + 1;
else
r = mid;
}
return l;
}
};
代码cpp2版本二
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (nums[mid - 1] < nums[mid])
l = mid;
else
r = mid - 1;
}
return l;
}
};
5.力扣153. 寻找旋转排序数组中的最小值
二分法：
利用选择数组得到二段性，在最小值点左侧的值都是大于最小值的，而且递增；最小值右侧的值都是大于最小值的，也是递增；同时最小值左侧的值都比右侧的大，根据nums[n - 1]为参照物(或者nums[0]为参照物,但要考虑递增数组的边界情况)，最小值左侧的值都大于nums[n - 1]，最小值右侧的值小于nums[n - 1]。
代码cpp
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, n = nums.size(), r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] < nums[n - 1])
r = mid;
else
l = mid + 1;
}
return nums[l];
}
};
6.力扣LCR 173. 点名
二分法：
这个题有很多方法，这里只讨论二分法，根据二段性，可以将区间分为左区间：下标值和数值相等，右区间：下标值不等于数值，而右区间的第一个元素的下标就是缺少的那个数。（特殊情况：不存在右区间，即全递增的数值，那么判断查找到位置的值是否等于下标就行）
代码cpp
class Solution {
public:
int takeAttendance(vector<int>& records) {
int l = 0, r = records.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (records[mid] == mid)
l = mid + 1;
else
r = mid;
}
if (records[l] == l)
return l + 1;
else
return l;
}
};