Search in Rotated Sorted Array leetcode

Suppose a sorted array 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.

下面是rotate后的一个有序数组的图。四边形的斜边表示数组中数值的大小。

在这种情况下数组分了两部分，分别都是有序（递增）的。

当我们计算了Mid以后，有两种可能，分别用Mid1和Mid2表示。

1. 如果A[Low] < A[Mid]，说明Mid落在区间1中,即图中Mid1的位置。那么，如果target小于A[Mid1]，那么继续在Low和Mid1中间搜索；否则，在Mid1和High中间搜索；

2. 如果A[Low] >= A[Mid]，说明Mid落在区间2中，即图中Mid2的位置。同理，如果target小于A[Mid2],那么继续在Low和Mid2中间搜索；否则，在Mid2和High中间搜索。

这样，平均地，我们每次剔除一半数据，

时间复杂度是O(logn) 空间O(1)。

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (nums[left] <= nums[mid]) {
                if (target < nums[mid] && target >= nums[left]) {
                    right = mid -1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

public class Solution {
    public int search(int[] A, int target) {
        if (A.length == 0 || A == null){
            return -1;
        }
        int start = 0;
        int end = A.length - 1;
        while (start + 1 < end){
            int mid = start + (end - start) / 2;
            if (A[mid] >= A[start]){// case Mid1
                if (target >= A[start] && target <= A[mid]){//
                    end = mid;
                } else {
                    start = mid;
                }
            } else { //case Mid2
                if (A[start] > target && A[mid] < target){
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }
        if (A[start] == target){
            return start;
        } else if (A[end] == target){
            return end;
        } else {
            return -1;
        }
    }
}