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

//这题可以用遍历水过但是这里我们采用一种非常装逼的二分法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        //这题直接遍历就能水过，二分的方法如下:
        //首先你要判断target位于哪个区间部分
        if(target==nums[0])
            return 0;
        return process(nums,0, nums.size()-1,target);
    }
    int process(vector<int >array,int low,int high,int k)
    {
        if(low>high)
            return -1;
        int mid=(low+high)/2;
        if(array[mid]==k)
            return mid;
        if(array[mid]<k&&k<array[0])//这句的意思是如果当前array[mid]的值和target的值都在较小的那一边数组里（右边的小数组里）此时在这个数组里所有的数都是升序的直接正常二分即可
           return process(array, mid+1,high, k);
        else if(array[mid]<k&&array[mid]>=array[0])//这句的意思是target和array【mid】的值都分布在左边较大的升序数组里，此时也正常二分即可
            return process(array, mid+1, high, k);        
       else if(array[mid]<k&&k>array[0]&&array[mid]<array[0])//这句的意思是target在左边的大数组里，array【mid】在右边的小数组里，你想如果此时想找到target肯定不可能正常二分，必须要让查找范围局限在左侧位置，所以要反着写
            return process(array, low, mid-1, k);

//下面array【mid】的值大于target的时候分析和上面一样
        if(array[mid]>k&&k>array[0])
           return process(array, low, mid-1,  k);
        else if(array[mid]>k&&array[mid]<array[0])
            return process(array, low, mid-1,  k);
         else if(array[mid]>k&&array[mid]>=array[0]&&k<array[0])
            return process(array, mid+1, high, k);
        else return -1;
    }
};