自己平时写二分全靠运气，运气好的时候就能水过二分，究其原因还是自己对二分的过程不了解清楚，因此专门写一个BLOG来记录刷爆二分的过程。
首先贴一个究极好用模板：https://www.pianshen.com/article/90471307044/
用二分法求解寻找有序序列中“第一个”满足某条件的元素的位置的模板：
//二分区间为左闭右闭的[left,right]
//解决“寻找有序序列第一个满足某条件A的元素的位置”
int solve(int left,int right){
int mid;
while(left<right){
mid=(left+right)>>1;
if(条件A成立){
right=mid;
}
else left=right+1;
}
return left;
}
T1
P704二分查找
我们考虑条件A是什么，题目要找到等于target的目标位置，因此我们查找的条件为：有序序列中第一个大于等于target的位置，如果这个位置对应的数是target，就说明找到了，如果不是，则不存在这个数，返回-1。代码如下：
int search(vector<int>& nums, int target) {
int n=nums.size();
int left=0,right=n-1;
int mid;
while(left<right){
mid=(left+right)>>1;
if(nums[mid]>=target) right=mid;
else left=mid+1;
}
if(nums[left]==target) return left;
else return -1;
}
本题可以分成两个二分来实现，第一个二分条件A为：寻找有序序列中第一个大于等于target的数的位置，查找到的第一个数如果不等于target，就说明数组中不存在target这个数，直接返回[-1,-1]，如果等于target的话，起始位置就是查找到的这个位置，再进行第二次二分查找，条件A未寻找有序数列中第一个大于target的位置，注意，如果不存在大于target的数，即target是最大的数，那么返回的值left是会停在n-1的位置的，因此特判以下即可，代码如下：
vector<int> searchRange(vector<int>& nums, int target) {
int n=nums.size();
vector<int>ans(2,-1);
if(n==0) return ans;
int left=0,right=n-1;
int mid;
while(left<right){
mid=(left+right)>>1;
if(nums[mid]>=target) right=mid;
else left=mid+1;
}
if(nums[left]==target) ans[0]=left;
else return ans;
left=0,right=n-1;
while(left<right){
mid=(left+right)>>1;
if(nums[mid]>target) right=mid;
else left=mid+1;
}
if(nums[left]==target) ans[1]=left; //特判一下target是否是最大的数
else ans[1]=left-1;
return ans;
}
T3
P33搜索旋转排序数组
本题要求即几乎有序的数组，查找某个元素是否存在问题，因此我们可以把数组一分为二，则一定有一段是完全有序，而另一段是基本有序，我们在完全有序的数组中二分查找，没找到就继续分基本有序的数组，直到left=right为止。代码如下：
int search(vector<int>& nums, int target) {
int n=nums.size();
int left=0,right=n-1;
int mid;
while(left<right){
mid=(left+right)>>1;
if(nums[mid]==target) return mid;
else if(nums[mid]<nums[right]){ //说明有序数组是[mid,right]，进行二分查找
if(nums[mid]>=target||nums[right]<target) right=mid; //注意条件
else left=mid+1;
}
else{ //有序数组是[left,mid]
if(nums[mid]>=target&&nums[left]<=target) right=mid;
else left=mid+1;
}
}
return nums[left]==target? left:-1;
}
写二分不能全靠模板，还是要真正自己理解