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

nums数组虽然在旋转过后仍然是有序的我们可以用二分。我们把数组看成两部分第一部分始终单调递增而且其中每一个元素一定比第二段大。而第二部分也是单调递增不过其最大值也比第一部分的最小值小。根据上述条件可以得到第一部分的第一个元素可以用来判断元素所在第一部分还是第二部分mid指针可能在第一部分也可能在第二部分因此第一个判断条件就是用nums[mid]比较和nums[left]的大小来判断当前mid的位置。得到mid所指向元素的下标的位置后就是用mid不断靠近目标值了用一个嵌套循环即可具体代码如下class Solution { public: int search(vectorint 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 mid1;//目标值在右边right进行逼近 } } else{ if(nums[mid] target target nums[right]){//(情况反的时候也同理见第12行) left mid1; } else{ right mid - 1; } } } return -1; } };