题目

讲解

题干和提示中一共给出了两个很重要的信息,一个是未旋转之前,数组是有序数组;第二个是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;
    }
}