Concise JAVA solution based on Binary Search


  • 0

    In the rotated array, there must be one half of the array is still in sorted order. We need to make a judgement to decide which half is ordered, and if the target in that half. If not, check the other half.

    Time complexity = O(lgn) - Special thanks to flyinghx61

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.