[LeetCode] Search in Rotated Sorted Array

Problem:

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: O(logn)

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

Key Concept: do similar binary search in possible session