专题三：二分查找模板：
根据题干分析，根据二分性，划分区间，得出二分最重要的几个要点：
- 判断条件：while(......) 是left<=right 还是left
- 求中点的方式：mid = left + (right-left)/2 还是 mid = left + (right-left+1)/2这个点很关键。如果和下面mid的迭代不相符，这便是第二个死循环的点。
- left和right的迭代：是left = mid还是left = mid+1、是right = mid还是right = mid -1这都是需要清除的问题。
1. 朴素二分模板：
while (left <= right) { int mid = left + (right - left) / 2; if (......) right = mid - 1; else if (......) left = mid + 1; else return mid; }
2. 区间左值模板：
特点: 左值：左动，下有+1上不加；
while(left<right) { int mid=left+(right-left)/2; if(...) left=mid+1; else right=mid; }
3. 区间右值模板：
特点: 右值：右动，下有-1上+1；
while(left<right) { int mid=left+(right-left+1)/2; if(...) right=mid-1; else left=mid; }
题目1：704. 二分查找
思路分析：
思路1：朴素二分查找O(logN)
代码实现：
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; if (nums[mid] > target) right = mid - 1; else if (nums[mid] < target) left = mid + 1; else return mid; } return -1; } };
题目2：34. 在排序数组中查找元素的第一个和最后一个位置
思路分析：
本题请看代码注释：主要三个点：判断条件、mid取值、left和right迭代
思路1：区间左右值二分查找 O(logN)
代码实现
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int left=0,right=nums.size()-1; int begin=-1,end=-1; if(nums.empty()) return {-1,-1}; //1.区间左端点查找： 二分区间：[小于目标值][大于等于目标值] left维护前者，right维护后置，目标值在right区间左端取到。 while(left<right) //判断：为什么不能等于，因为最终结果是left=right处取到，=就死循环 { int mid=left+(right-left)/2; //当还剩最后left和right相邻时，指向左端点，结合迭代，左端点可以跳出来，右端点不能。 if(nums[mid]>=target) right=mid; //right不跳出区间，因为可能目标值就是right处 else left=mid+1; //left需要移动，因为目标值一定不在它的区间 } if(target==nums[left]) begin=left; //2.区间左端点查找： right=nums.size()-1; //注意更新left和right，优化：右端点一定在左端点后，所以left可以不更新，就处于左端点处 while(left<right) { int mid=left+(right-left+1)/2; if(nums[mid]>target) right=mid-1; else left=mid; } if(target==nums[left]) end=left; return {begin,end}; } };
