33 Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/#/description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

分析及代码

方法是：https://discuss.leetcode.com/topic/3538/concise-o-log-n-binary-search-solution/2

找到最小的那个值，那个位置就是旋转的值 //这个方法还挺重要的

进行正常的二分搜索，但是每次真正的mid的位置都是旋转后的位置

public int search(int[] nums, int target) {
    if(nums.length == 0) {
        return -1;
    }
    int len = nums.length;
    int l = 0, r = len - 1;
    while(l < r) {
        int mid = l + (r - l) / 2;
        if(nums[mid] > nums[r]) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    int rotate = l;
    l = 0;
    r = len - 1;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        int realmid = (mid + rotate) % len;
        if(nums[realmid] == target) {
            return realmid;
        } else if(nums[realmid] < target) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return -1;
}

时间复杂度是O(nlogn)