Search in Rotated Sorted Array

Search in Rotated Sorted Array

问题：

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.

思路：

　　二分查找

我的代码：

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

他人代码：

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

学习之处：

• 对于rotate array 二分一刀下去，总有一半是可以判断是否有序的。
• left + 1 < right 后面会剩余一个或者两个数字需进一步判断 left <= right catch 到了所有的数据