二分查找
什么是二分查找:就是定义左右2个指针(此指针非真指针)取中间值
通过一次次取中间值找到要找到的数
二分的实战+讲解
二分查找
题目:地址
题目解析:
找到一个等于target的值
并返回他的下标
题目中给的数组是升序的
题目讲解
这样就能找到要找的目标值
如果没有找到那么就可以返回-1
代码:
class Solution {
public:
int search(vector<int>& nums, int target)
{
int left = 0,right =nums.size()-1,sum = 0;
while(left<=right)
{
sum = left+(right-left+1)/2;//这里的+1要不要无所谓在这个题
if(nums[sum]<target)
{
left=sum+1;
}
else if (nums[sum]>target)
{
right = sum-1;
}
else
{
return sum;
}
}
return -1;
}
};
普通二分模版
在排序数组中查找元素的第一个和最后一个位置
题目:地址
题目解析:
找到等于target的第一个下标和最后一个下标
并且返回
数组是升序的
题目讲解
代码:
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target)
{
if(nums.size()==0)
{
return {
-1,-1};
}
int left=0,right=nums.size()-1;
int mid = 0;
int begin = 0,end = 0;
while(left<right)
//找左端点
//不能写等于
//因为写了等于会死循环
//right位置不改变
//mid位置会永远不动
{
//这里的不能写成right-left+1的形式
//如果写了会出现死循环
//同样的 right位置不改变
//mid也不会动 进而死循环
mid = left+(right-left)/2;
if(nums[mid]>=target)
{
right=mid;
}
else
{
left=mid+1;
}
}
if(nums[left]==target)
{
begin=left;
}
else
{
return {
-1,-1};
}
right=nums.size()-1;
while(left<right)
{
//这里的不能写成right-left的形式
//如果写了会出现死循环
//同样的 left位置不改变
//mid也不会动 进而死循环
mid = left+(right-left+1)/2;
if(nums[mid]>target)
{
right=mid-1;
}
else
{
left=mid;
}
}
end = right;
return {
begin,end};
}
};
万能二分模版
总结
二分的模版很简单
但是不能死记硬背
要理解里面为什么这样子二分
死记硬背改了一种形式也不一定你能看出是二分
最后喜欢的点点赞
可能这也不是最优的优化，但是我能做出来现阶段最好的了。
