LeetCode-33-搜索旋转排序数组

题目

LeetCode-33-搜索旋转排序数组

讲解

题干和提示中一共给出了两个很重要的信息，一个是未旋转之前，数组是有序数组；第二个是nums中的每个值都独一无二；并且最后说明了时间复杂度为O(log n)，看到log，先想到二分

还是万年不变的y总二分模板

我们从这两条信息可以想到，如果用二分法去分割这个数组，则肯定是一个区间为有序，另一个区间为无序；
然后看一下这个有序的区间，target可以通过对左右两边界的对比，得知这个数是否在有序区间里，如果在，则对这个有序区间进行二分，如果不是，则target肯定是在无序区间，在无序区间中二分也是一个道理，肯定回出现一个有序一个无序，然后继续判断即可，最终得出结果。

题解

public int search(int[] nums, int target) {
    int l = 0, r = nums.length-1;
    while(l < r){
        int mid = (l+r)/2;
        // 即左分区有序
        if(nums[l] < nums[mid]){
            //即target在左区间出现
            if(nums[l]<=target && nums[mid]>=target){
                r = mid;
            }else{
                l = mid+1;
            }
        }else{ //即右分区有序
            //即target在右区间出现
            if(nums[mid+1]<=target && nums[r]>=target){
                l = mid+1;
            }else{
                r = mid;
            }
        }
    }
    if(nums[l] == target){
        return l;
    }else{
        return -1;
    }
}