Find rotate index and binary search, O(logN) 4ms C++, 156ms C#


  • 0
    L

    It's two steps to solve,

    1. search rotateIndex (binary search)

    2. binary search target, range is (start ~ rotateIndex-1) or (rotateIndex~end).

    All of steps are O(log N) time, the solution is O(log N) time.

    C++ code: (4ms)

    int findRotateIndex(vector<int>& nums){
    	int left = 0;
    	int right = nums.size() - 1;
    	while (left < right){
    		int mid = (left + right) >> 1;
    		if (nums[right] < nums[mid]) left = mid + 1;
    		else right = mid;
    	}
    	return left;
    }
    
    int search(vector<int>& nums, int target) {
    	int left = 0;
    	int right = nums.size() - 1;
    	int rotateIndex = findRotateIndex(nums);
    	// nums[rotateIndex] is smallest in nums
    	// (start -- target --) rotateIndex -- end	
    	if (target > nums[right]) right = rotateIndex - 1;
    	// start -- (rotateIndex -- target -- end)
    	else if (target < nums[right]) left = rotateIndex;
    	else return right;
    
    	// binary search
    	while (left <= right){
    		int mid = (left + right) >> 1;
    		if (nums[mid] < target) left = mid + 1;
    		else if (nums[mid] > target) right = mid - 1;
    		else return mid;
    	}
    	return -1;
    }
    

    C# code (156ms)

    public int Search(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;
        int rotateIndex = findRotateIndex(nums);
        // nums[rotateIndex] is smallest in nums
        // (start -- target --) rotateIndex -- end  
        if (target > nums[right]) right = rotateIndex - 1;
        // start -- (rotateIndex -- target -- end)
        else if (target < nums[right]) left = rotateIndex;
        else return right;
        int result = Array.BinarySearch(nums, left, right - left + 1, target);
        if(result >= 0) return result;
        return -1;
    }
    
    int findRotateIndex(int[] nums){
        int left = 0;
        int right = nums.Length - 1;
        while (left < right){
            int mid = (left + right) >> 1;
            if (nums[right] < nums[mid]) left = mid + 1;
            else right = mid;
        }
        return left;
    }

Log in to reply
 

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