二分查找算法

二分查找

什么是二分查找:就是定义左右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};}
};

万能二分模版

总结

二分的模版很简单
但是不能死记硬背
要理解里面为什么这样子二分
死记硬背改了一种形式也不一定你能看出是二分
最后喜欢的点点赞
可能这也不是最优的优化，但是我能做出来现阶段最好的了。