总有一天,你会站在最亮的地方,活成自己曾经渴望的模样—— 苑子文 & 苑子豪《我们都一样 年轻又彷徨》
二分算法是一种非常强大的算法!!! 想象你在一本厚厚的字典里查找一个词。这本字典的词都是按字母顺序排列的。如果你像小学生学习拼音那样一页一页翻,肯定效率很低,因为这样你要查很久。二分查找算法就像是一个聪明的查词策略,它可以帮你快速定位到那个词。
使用二分查找时:
通过这样一分为二,一步步缩小范围的方式,直到找到那个词,这个过程就是二分查找。 这个方法之所以有效,是因为每次查找你都排除了一半的可能性,大大提高了查找效率。就像在一个有序的环境中找东西,知道了规则,就能迅速定位,节省了大量的时间。
二分查找主要有三种模版:朴素算法,左端点算法,右端点算法。下面我们一起来通过题目认识二分查找算法吧!
上链接!!!704. 二分查找
这是一一道非常经典的二分查找题目,我们来看样例:
很好理解二分查找的寻找过程,下面我们来看代码。
这道题无需考虑很多,使用朴素二分查找即可:
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0 , right = nums.size() - 1;
while(left <= right)
{
int mid = left + (right - left) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
};
下面的题目我们来详细讲解左端点二分和右端点二分!
上链接!!!34. 在排序数组中查找元素的第一个和最后一个位置
这道题分别要寻找目标值的开始索引和终止索引。来看样例:
先来看暴力算法,遍历所有的元素,记录起始和终止位置既可以,但是这样就浪费了数组有序的重要特性!!! 那使用朴素算法呢? 可以是可以,但是时间复杂度会很大!遇到数组全部是目标值的时候,第一次就能命中对应目标值,但要寻找到起始和中止就要遍历所有的元素,这样就和暴力算法没有区别了!所以不推荐朴素算法
我们来看朴素算法的优化版本:左端点二分和右端点二分 这道题实际上可以分成两个问题:
先看左端点:我们可以把数组分为两部分:小于target 的部分 ,大于等于target 的部分。然后我们分类讨论(x 为 中间值):
在来看难点 : 循环条件 和 求中点的操作
到底是left < right 还是 left <= right ???我们来分类讨论一下:
求中点也是有两种:
如果仅剩两个元素时,使用第二种时,如x >= t 那么right 就不动了!!!陷入了死循环!!! 所以要使用第一种!!!
右端点也是同样的分析思路,不同的是:
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0) return {-1,-1};
int begin = 0 , end = 0;
int left = 0, right = nums.size() - 1;
//先找左点
//左边都小于 t 右边大于等于 t
//左边不合法 右边合法
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] < target) left = mid + 1;
else right = mid;
}
if(nums[left] == target) begin = left;
else return {-1,-1};
//进行右边操作
//左边都小于等于 t 右边大于 t
//左边合法 右边不合法
left = 0, right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(nums[mid] <= target) left = mid;
else right = mid - 1;
}
end = right;
return {begin,end};
}
};
提交就过啦!!!
家人们!!!上链接!!!35. 搜索插入位置
这道题很好理解,找到对应位置插入即可!!!
当然暴力算法很好想,但是我们不用。 通过上一道题的思路,我们很容易想到使用左端点二分的方法,因为插入是在该数的前面插入。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0 , right = nums.size() - 1;
int ans = 0;
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] < target) left = mid + 1;
else right = mid;
}
//避免比最大的数大,此时是在后面插入
if(left == nums.size() - 1 && target > nums[left]) ans = left + 1;
else ans = left;
return ans ;
}
};
提交!过啦!!!!
上链接!!!69. x 的平方根
这道题很好理解奥,我们要实现找到算术平方根。即平方小于x 的最大的数。
暴力算法很好想,一个一个试就可以,但是使用二分算法更加快速。 我们可以把数字抽象为左右端,left 为 0 right = x 。然后开始二分(判断条件是mid 的平方与x的比较)。因为是找最大的所以使用右端点二分。
class Solution {
public:
int mySqrt(int x) {
//初始化 右值设置为 x 的一半进一步可以避免平方超范围
int left = 0 , right = x / 2 + 1;
while(left < right)
{ // 使用long long =防止超出int范围
long long mid = left + (right - left + 1) / 2;
if(mid * mid <= x) left = mid ;
else right = mid - 1 ;
}
return left;
}
};
提交:过啦!!!!