1.概念
二分查找一般用于有序的序列，将序列一分为二，通过比较中间值与目标值，舍弃一半的区间，只在剩下的一半区间内继续查找，时间复杂度为O(logn)。
二分查找常用模板：
while(left<=right){ //1
int mid = left + (right-left)/2; //2
if(nums[mid]==target){ }
else if (nums[mid]<target){
left = mid + 1; //3
}else{
right = mid -1; //4
}
}根据不同的题目，上述代码中的1,3,4处需要做不同修改，2处是为了防止溢出。
3,4处决定了区间的开闭情况。
2.题目
1）力扣
https://leetcode.cn/problems/sqrtx/解题思路：这道题需要找到一个整数a，是满足a^2<=x的最大整数。
所以可以直接在[0,x]的范围内应用二分查找。
又因为要用到x/mid来判断是否找到目标值，0不能做被除数，所以0另外考虑。
代码：
class Solution {
public:
int mySqrt(int x) {
if(x==0) return 0;
int left = 1, right = x;
while(left<=right){
int mid = left + (right-left)/2;
int t = x/mid;
if(t==mid){
return mid;
}else if (t>mid){
left = mid + 1;
}else{
right = mid - 1;
}
}
return right;
}
};这道题也可以用牛顿迭代法来做，公式：
2）力扣https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/这题需要用二分查找，分别找到满足目标值区间的左边界和右边界。
找左边界的时候，需注意当中间值与目标值相等时，应该选择左边区间，因为要找的是左边界，肯定是在中间值左边（或者就是中间值）
找右边界的时候，需注意当中间值与目标值相等时，应该选择右边区间，因为要找的是右边界，肯定是在中间值右边（或者就是中间值）
至于区间的取法，左闭右开，左闭右闭都可以，只是上下文对坐标的处理会不同。
我的做法比较直观，找左边界的时候，区间取左闭右闭，最后是返回左指针。
找右边界的时候，区间也是取左闭右闭，最后是返回右指针。
相当于找左边最小的等于目标值的坐标，和右边最大的等于目标值的坐标。
如果做这类题目，觉得模板种的1,3,4很混乱，不知道该怎么取，那可以先直接写一版，case报错了，再依次调整1,3,4处。
代码：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size()==0) return vector<int>({-1,-1});
int left = findLeft(nums,target), right = findRight(nums,target);
if(left>right) left=right=-1;
return vector<int>({ left, right});
}
int findLeft(vector<int>& nums, int target){
int left = 0, right = nums.size()-1, mid;
while(left<=right){
mid = left + (right-left)/2;
if(nums[mid]<target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return left;
}
int findRight(vector<int>& nums, int target){
int left = 0, right = nums.size()-1, mid;
while(left<=right){
mid = left + (right-left)/2;
if(nums[mid]>target){
right = mid -1;
}else{
left = mid + 1;
}
}
return right;
}
};