算法修炼之路之二分查找

目录

一:三大二分介绍及模板

1.普通二分

2.查找左右边界的二分及模板 

二:LeetCode OJ练习

1.第一题

2.第二题 

 3.第三题

 4.第四题

 5.第五题

 6.第六题

一:三大二分介绍及模板

1.普通二分

这里通过一道题来引出普通二分及模板

LeetCode_704 二分查找

画图分析:

 

具体代码:

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) right=mid-1;else if(nums[mid]<target) left=mid+1;else return mid;}return -1;}

普通二分模板

 

2.查找左右边界的二分及模板 

 通过题来引出

LeetCode_34 在排序数组中查找元素的第一个和最后一个位置

画图分析:

 

具体代码:

vector<int> searchRange(vector<int>& nums, int target) {//处理边界情况if(nums.size()==0) return {-1,-1};int left=0,right=nums.size()-1;int begin=0;//查找左端点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};//查找右端点left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]>target) right=mid-1;else left=mid;}return {begin,left};}

左右边界的二分模板: 

二:LeetCode OJ练习

1.第一题

LeetCode_69 x的平方根

画图分析:

 

具体代码:

int mySqrt(int x) {//处理边界情况if(x<1) return 0;int left=1,right=x;//防止当x=INT_MAX时，right-0+1操作直接越界的while(left<right){long long mid=left+(right-left+1)/2;//防止越界if(mid*mid>x) right=mid-1;else left=mid;}return left;}

2.第二题 

 LeetCode_35 搜索插入位置

画图分析:

 

具体代码:

 int searchInsert(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) left=mid+1;else right=mid;}//处理在数组末尾插入的情况if(nums[left]<target) return left+1;else return left;}

 3.第三题

LeetCode_852 山脉数组的峰顶索引

画图分析:

 

具体代码:

 int peakIndexInMountainArray(vector<int>& arr) {int left=1,right=arr.size()-2;//首尾不可能是结果while(left<right){int mid=left+(right-left+1)/2;if(arr[mid]>arr[mid-1]) left=mid;else right=mid-1;}return left;}

 4.第四题

LeetCode_162 寻找峰值

 画图分析:

具体代码:

 int findPeakElement(vector<int>& nums) {int left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]>nums[mid+1]) right=mid;else left=mid+1;}return left;}

 5.第五题

LeetCode_153 寻找旋转排序数组中的最小值

画图分析:

 

具体代码:

int findMin(vector<int>& nums) {int left=0,right=nums.size()-1;int t=nums[right];while(left<right){int mid=left+(right-left)/2;if(nums[mid]>t) left=mid+1;else right=mid;}return nums[left];}

 6.第六题

LeetCode_LCR 173 点名

画图分析:

 

具体代码：

int takeAttendance(vector<int>& records) {int left=0,right=records.size()-1;while(left<right){int mid=left+(right-left)/2;if(records[mid]==mid) left=mid+1;else right=mid;}//处理细节问题return records[left]==left? left+1:left;}