Searching Rotated array

Problem 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,7] might become [4,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.Your algorithm’s runtime complexity must be in the order of O(log n).

Examples

Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output:: 4

Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:
Input: nums = [1, 3, 5], target = 1
Output: 0

Solution

　　一开始看到这道题，做过同样的找最小值问题。以为是道水题。没想到坑的一P。卡了三个小时。在判断那翻来覆去。一开始想找到最小值。再判读target是在前半段还是后半段。再二分。时间复杂度是0（logn+logn）=O(logn) . 但是蜜汁超时。嗨呀然后就开始了反复挣扎的三小时if判断挣扎。修好了一个坑又出现另一个坑。看了解析恍然大悟。这道题和最小值无关。旋转数组有一个特性。最小值前旋转数组前是递增的，最小值后旋转数组是递增的。
　　如果中间的值比左端的值大，则左侧数组必然有序。
　　如果中间的值比左端的值小，则右侧数组必然有序。

Code

 public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int low = 0, high = nums.length - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] >= nums[low]) {
            if (nums[mid] > target && target >= nums[low]) {
                high = mid - 1;//Target is in the left which is order.
            } else {
                low = mid + 1;//Target is in the right which may be disorder.
            }
        } else {
            if (nums[mid] < target && target <= nums[high]) {
                low = mid + 1;//Target is in the right which is order.
            } else {
                high = mid - 1;//Target is in the left which may be disorder.
            }
        }
    }
    return -1;
}