4ms O(lgn) based on binary search without finding the rotate point


  • 0
    B
    int search(vector<int>& nums, int target) {
    	int  l = 0, r = nums.size() - 1;
    	return fsearch(nums, l, r, target);
    }
    //common binary search
    int bsearch(vector<int>& nums, int l, int r, int target) {
    	int mid;
    	while (l <= r) {
    		mid = (l + r) / 2;
    		if (nums[mid] < target)
    			l = mid + 1;
    		else if (nums[mid] > target)
    			r = mid - 1;
    		else
    			return mid;
    	}
    	return -1;
    }
    int fsearch(vector<int>& nums,int l,int r, int target) {
    	int mid,flag=-1;
    	if (l > r)
    		return flag;
    	mid = (r + l) / 2;
    	if (nums[mid] == target)
    		return mid;
    	else if(nums[mid]==nums[l])//in case only two numbers
    		flag= bsearch(nums, l+1, r, target);
    	else if (nums[l] < nums[r])//in case nums has already in order
    		flag = bsearch(nums, l, r, target);
    
    	else if (nums[mid] > nums[l] && nums[mid] < target) 
    		flag=fsearch(nums, mid + 1, r, target);
    	else if (nums[mid] < nums[l] && nums[mid] > target) 
    		flag = fsearch(nums, l, mid-1, target);
    	else{
    		flag = fsearch(nums, l, mid - 1, target);
    		flag=(flag==-1)?fsearch(nums, mid + 1, r, target):flag;
    	}
    	return flag;
    }

Log in to reply
 

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