二分查找的应用

什么时候用二分查找？

数据具有二段性的时候

第一题：

 题解代码：

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;//中间，left+区间长度if(nums[mid]>target){right = mid-1;}else if(nums[mid]<target){left = mid+1;}else return mid;}return -1;}
};

总结朴素二分查找的模板：

while(left<=right){//切记这里是<=int mid = left+ (right-left)/2;//防止溢出的写法if(..........){right = mid-1;}else if(............){left = mid+1;}else return ........;}

第二题：

题解代码：

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 begin = 0;//二分⬅左端点while(left<right){//求中间int mid = left+(right-left)/2;if(target>nums[mid]) left = mid +1;else right = mid;}//判断是否有结果if(nums[left] != target) return {-1,-1};else begin = left;//二分右端点right  = nums.size()-1;while(left<right){int mid = left+(right-left+1)/2;if(target>= nums[mid]) left = mid;else right = mid-1;}return {begin,right};}
};

总结二分模板：

1、查找区间左端点的模板

//查找区间左端点的模板 
while(left<right){//求中间int mid = left+(right-left)/2;if(、、、、、、) left = mid +1;else right = mid;}

2、查找区间有端点的模板：

while(left<right){int mid = left+(right-left+1)/2;if(、、、、、) left = mid;else right = mid-1;}

3、帮助记忆的几句话：

1、下面用减上面就用加1；

2、下面按情况讨论；

第三题： 

题解代码：

class Solution {
public:int mySqrt(int x) {//处理特殊的额情况if(x<1) return 0;int left = 1,right = x;//固定的模板 while(left<right){long long mid = left+(right-left+1)/2;if(mid*mid<=x) left = mid;else right = mid-1;}return left;}
};

 第四题：

题解代码：

class Solution {
public: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) right = mid;else left = mid+1;}//处理一下特殊的情况if(nums[left]< target) return nums.size();return left;}
};

第五题：

题解思路：

 

所以代码如下：

class Solution {
public: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;}
};