1二分查找：在有序集合搜索特定值的过程，每次比较之后将查找空间一分为二。
target:要查找的值 index:当前位置 left,right:维持查找空间的指标
mid:用来确定向左查还是向右查的索引
查找空间: [left,right]
二分查找维护left，right，mid，并将target和索引为mid的值进行比较；
如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半继续查找，直到成功为止
第一种情况：
int bsearch(int l, int r):while (l < r)int mid = (l + r + 1)>>1;if (check(mid)) l = midelse r = mid - 1return l第二种情况：右面第一个符合条件的下标。
注意讨论r=n-1的情况。
如果没有数符合条件，那么r最终就停在n-1的位置。
int bsearch(int l, int r)while (l < r)int mid=l+(r-l)/2;if(check(mid))r = mid;else l=mid + 1;return l;给定一个数组，需要判断数组长度。
比如访问到idx-1和idx+1时，长度必须大于等于3.
数组中查找数
search(vector<int>& nums, int target) {l=0;r=n-1;while(l<=r)mid=l+(r-l)/2;if(target==nums[mid]) return mid;else if(target<nums[mid]) r=mid-1;else l=mid+1;return -1;x的平方根
二分答案
long long mySqrt(int x):if(x==0)return 0;if(x==1||x==2||x==3) return 1;//否则从2开始到x/2搜索哪个的平方等于x或者哪两个数的平方之间包含xlong long l=2;//用long long类型防止溢出long long r=x/2;//平方只能在【2~x/2】中的某个数出现while(l<=r):long long mid=l+(r-l)/2;if(mid*mid==x||mid*mid<x&&(mid+1)*(mid+1)>x)//mid符合条件return mid;if (mid*mid<x) l=mid+1;else r=mid-1;return -1;leetcode 33. 搜索旋转排序数组
int search(vector<int>& nums, int target) {int l=0;int r=nums.size()-1;if(nums.size()==1&&nums[0]==target)return 0;if(nums.size()==1&&nums[0]!=target)return -1;while(l<r)int mid=l+(r-l)/2;if(nums[mid]<nums[0])r=mid;else l=mid+1;//r为右面第一个比nums[0]小的下标if(r==nums.size()-1&&nums[r]>nums[0])l=0;r=nums.size()-1;elseif(target>=nums[0]) l=0; r--;else l=r; r=nums.size()-1;while(l<r)int mid=l+(r-l)/2;if(nums[mid]>=target)r=mid;else l=mid+1;if(nums[r]==target)return r;return -1;leetcode 852. 山脉数组的峰顶索引
int peakIndex(vector<int>& arr)int l=0;int r=arr.size()-1;while(l<r)int mid=l+(r-l)/2;if(mid-1>=0&&mid+1<arr.size()&&arr[mid]<arr[mid-1]&&arr[mid]>arr[mid+1])r=mid;else l=mid+1;return r-1;
leetcode1095. 山脉数组中查找目标值
用二分法找到峰值（见上题)
while用if条件语句如果有访问数组索引+或-的操作，要防止数组越界。
class Solution {
public:int findInMountainArray(int target, MountainArray &m) {int n=m.length();int l=0;int r=n-1;while(l<r){int mid=l+(r-l)/2;if(mid-1>=0&&mid+1<n&&m.get(mid)<m.get(mid-1)&&m.get(mid)>m.get(mid+1))r=mid;else l=mid+1;}int idx=r-1;//注意是r-1l=0;r=idx;while(l<r){int mid=l+(r-l)/2;if(m.get(mid)>=target)r=mid;else l=mid+1;}if(m.get(r)==target)return r;l=idx+1;r=n-1;while(l<r){int mid=l+(r-l)/2;if(m.get(mid)<=target)r=mid;else l=mid+1;}if(m.get(r)==target)return r;return -1;}
};
