题解 | #在旋转过的有序数组中寻找目标值#

C++版本---
如若有错误的或者可以改进的地方，欢迎指正、交流

// NC48在旋转过的有序数组中寻找目标值--
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
/*          思路：
            将target和左 、中 、右 3个位置的值进行比对，以确定继续查找的区间
            其实就是判断以中点划分的左右区间是否有序
            因为旋转的那部分可长可短，中点可能在有序的那段，也可能跨段了，且肯定有一段有序
            如果 nums[mid]=target,返回
            如果 nums[left] <= nums[mid]  && nums[left] <= target < nums[mid]  那么接下来左边找 ,如果不是这样就是在右边
            如果 nums[mid] < nums[right]  && nums[mid] < target <=nums[right]  那么接下来右边找，反之左边
        注意点：
            1、nums[left] <= nums[mid] 要等号，比如只有两个数据的时候，nums[left]==nums[mid];此时如果不是左边这个，就找右边的
            2、nums[left] <= target < nums[mid] 左边取等号，查找的数可能位于最左边，最终mid=left
            3、nums[mid] < target <=nums[right] 右边取等号，查找的数可能位于最左边，最终mid=right

 */        int len=nums.size();
        if(len==0) return -1;
        int left=0,right=len-1;

        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target) return mid;
            // 看左边这段是否连续，要么连续，要么不连续
            //如果左边有序
            if(nums[left]<=nums[mid] ){
                if( nums[left]<= target && target < nums[mid]){
                    // 目标值在左边区间
                    right=mid-1;
                }else{
                    //如果不在左边，就去右边找
                    left=mid+1;
                }
            }else{
                //如果左边这段不连续，也就是nums[left]>nums[mid]，那么右边肯定连续
                //先看目标值是否在右边
                if(nums[mid]<target && target <= nums[right]){
                    // 如果在右边
                    left=mid+1;
                }else{
                    //如果在左边
                    right=mid-1;
                }
            }    
        }
        return -1;
    }
};