O(log N) solution, 2 pass with explanation


  • 0
    public class Solution {
    	    public int search(int[] nums, int target) {
    	        //find reverse point
    	    	int begin = 0 , end = nums.length;
    	    	while(end > begin+1){
    	    		int mid = begin + (end - begin)/2;
    	    		if(nums[mid] > nums[begin])begin = mid;
    	    		else end = mid;
    	    	}
    	    	//now mid point at the front sorted array's tail
    	    	int mid = end;
    	    	//reset begin and end
    	    	begin = 0;
    	    	end = nums.length;
    	    	if(target < nums[0]) begin = mid;
    	    	else end = mid;
    	    	//binary search in that area
    	    	while(end > begin){
    	    		int middle = begin + (end - begin)/2;
    	    		if(nums[middle] == target) return middle;
    	    		if(target > nums[middle]) begin = middle+1;
    	    		else end = middle;
    	    	}
    	    	return -1;
    	    }
    }
    
    

Log in to reply
 

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