Monday, April 22, 2013

Leetcode: Search in Rotated Sorted Array in Java

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.

Solution:

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

No comments:

Post a Comment