33.搜索旋转排序数组力扣

nums数组虽然在旋转过后仍然是有序的，我们可以用二分。我们把数组看成两部分，第一部分始终单调递增而且其中每一个元素一定比第二段大。而第二部分也是单调递增不过其最大值也比第一部分的最小值小。

根据上述条件可以得到：第一部分的第一个元素可以用来判断元素所在第一部分还是第二部分

mid指针可能在第一部分也可能在第二部分，因此第一个判断条件就是用nums[mid]比较和nums[left]的大小来判断当前mid的位置。

得到mid所指向元素的下标的位置后就是用mid不断靠近目标值了，用一个嵌套循环即可，具体代码如下：

class Solution { public: int search(vector<int>& nums, int target) { int n = nums.size(); int left = 0,right = n-1; while(left <= right){ int mid = (left + right)/2; if(nums[mid] == target){ return mid; } if(nums[left] <= nums[mid]){//一定要有等于，不然会算到第二部分去 if(nums[left] <= target && nums[mid] > target){//这里包含了一种隐藏情况就是当猜的mid在第一部分而target在第二部分那么就会小于nums[left]从而知道target在右边 right = mid - 1;//目标值在左边right进行逼近 } else{ left = mid+1;//目标值在右边right进行逼近 } } else{ if(nums[mid] < target && target <= nums[right]){//(情况反的时候也同理见第12行) left = mid+1; } else{ right = mid - 1; } } } return -1; } };