int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;
}

不断缩小区间范围只能遵循一种规律那就是由int mid = l + r >> 1;决定的从小到大找和l = mid + 1; （一定是匹配出现的），或者是由int mid = l + r+1 >> 1;决定的从大到小找和l = mid ; 这里

if(target>=nums[mid]&&target<=nums[r]){if(nums[mid] == target) return mid;else l=mid+1;	
}

如果此时不提前判断mid及时返回mid，那么l应当取的值是l=mid，显然不对（记住死循环解释） OK，提前判断mid，ac啦

class Solution {
public:int search(vector& nums, int target) {int n=nums.size();if(n==0)return -1;if(n==1)return nums[0]==target?0:-1;int l=0,r=n-1;while(lint mid=(l+r)>>1;
//		if(nums[mid] == target) return mid;
//     数组旋转过后一定是一段或者两段上升的子段，仍然可以二分
//     但是整体二分[l,mid]不一定恰好处于上升子段之中，可能包含了俩子段各一部分if(nums[l]<=nums[mid]){//不取等号是因为不存在重复元素 [l,mid]恰好处于升序子段if(target>=nums[l]&&target<=nums[mid]){r=mid;	}else l=mid+1;}else{//[l,mid]不完全处于升序子段，好办，[mid+1,r]一定属于if(target>=nums[mid]&&target<=nums[r]){if(nums[mid] == target) return mid;else l=mid+1;	}else r=mid-1;}}return (nums[l] == target)?l:-1;}
};//3 1  
//1 
//-1 其实是1

另一种二分代码

class Solution {
public:int search(vector& nums, int target) {int n=nums.size();if(n==0)return -1;if(n==1)return nums[0]==target?0:-1;
//      if(n==2){
//      	if(target==nums[0])return 0;
//      	else if(target==nums[1])return 1;
//      	else return -1;
//	  }int l=0,r=n-1;while(l<=r){int mid=(l+r)>>1;if(nums[mid] == target) return mid;
//     数组旋转过后一定是一段或者两段上升的子段，仍然可以二分
//     但是整体二分[l,mid]不一定恰好处于上升子段之中，可能包含了俩子段各一部分if(nums[l]//[l,mid]恰好处于升序子段//不取等号是因为不存在重复元素 ,错，要取， 比如 3 1 找1，l就是mid
//      	5 1 2 3 4找1，只要target找的范围缩小到了旋转点+左 或 右转点+左if(target>=nums[l]&&targetr=mid-1;	}else l=mid+1;}else{//[l,mid]不完全处于升序子段，好办，[mid+1,r]一定属于if(target>nums[mid]&&target<=nums[r]){l=mid+1;	}else r=mid-1;}}return -1;}
};

搜索旋转排序数组II

10111 和 11101 这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。

顺带发现，if(nums[mid] == target) return true;用我的二分模板，每次得到mid先判断也无伤大雅，提前发现提前返回而已，主要是注意缩小区间的方式

class Solution {
public:int search(vector& nums, int target) {int n=nums.size();if(n==0)return -1;if(n==1)return nums[0]==target?true:false;int l=0,r=n-1;while(lint mid=(l+r)>>1;if(nums[mid] == target) return true;if (nums[l] == nums[mid] && nums[mid] == nums[r]) {++l;--r;}else if(nums[l]<=nums[mid]){//不取等号是因为不存在重复元素 [l,mid]恰好处于升序子段if(target>=nums[l]&&target<=nums[mid]){r=mid;	}else l=mid+1;}else{//[l,mid]不完全处于升序子段，好办，[mid+1,r]一定属于if(target>=nums[mid]&&target<=nums[r]){if(nums[mid] == target) return true;else l=mid+1;	}else r=mid-1;}}return (nums[l] == target)?true:false;}
};//3 1  
//1 
//-1 其实是1

寻找旋转排序数组中的最小值

三种情况主要就是mid落在的位置不同，需要使区间来到第二段

class Solution {
public:int findMin(vector& nums) {int n=nums.size();int l=0,r=n-1;while(lint mid=l+r>>1;
//经由 1 到 n 次 旋转，两段升序子序列，且第一段大于第二段，最小值一定在第二段if(nums[mid]
//				l=mid;r=mid;}else{
//				r=mid-1;//不对的，记住永远在 第二段 找，lr需要使区间缩小到第二段l=mid+1;}}return nums[l];}
};

寻找旋转排序数组中的最小值II

class Solution {
public:int findMin(vector& nums) {int n=nums.size();int l=0,r=n-1;while(lint mid=l+r>>1;
//经由 1 到 n 次 旋转，两段升序子序列，且第一段大于第二段，最小值一定在第二段if(nums[mid]
//				l=mid;r=mid;}else if(nums[mid]>nums[r]){
//				r=mid-1;//不对的，记住永远在 第二段 找，lr需要使区间缩小到第二段l=mid+1;}else {//if(nums[mid]==nums[r])r--;}}return nums[l];}
};