二分查找

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

萬能二分模版

總結

二分的模版很簡單
但是不能死記硬背
要理解里面為什么這樣子二分
死記硬背改了一種形式也不一定你能看出是二分
最后喜歡的點點贊
可能這也不是最優的優化，但是我能做出來現階段最好的了。