My c++ 4ms solution by finding pivot with comment


  • 0
    S

    Hope this may help you :)

    class Solution 
    {
    public:
    int search(vector<int>& nums, int target)
    {
    	int length = nums.size();
    	int left = 0, right = length - 1, mid;
    	int pivot = -1;
    	//decide whether there is a rotation
    	if (nums[0] > nums[length-1])
    	{
    		//find pivot
    		while (left <= right)
    		{
    			mid = (left + right) / 2;
    			if (nums[mid] >= nums[0])
    			{
    				left = mid + 1;
    			}
    			else if (nums[mid] < nums[0])
    			{
    				right = mid - 1;
    			}
    		}
    		pivot = left;
    	}
    	
    	//find search range
    	if (pivot != -1)
    	{
    		if (target >= nums[0])
    		{
    			left = 0;
    			right = pivot - 1;
    		}
    		else
    		{
    			left = pivot;
    			right = length - 1;
    		}
    	}
    	else
    	{
    		left = 0;
    		right = length - 1;
    	}
    	
    	//binary search
    	while (left <= right)
    	{
    		mid = (left + right) / 2;
    		if (nums[mid] == target)
    		{
    			return mid;
    		}
    		else if (nums[mid] > target)
    		{
    			right = mid - 1;
    		}
    		else
    		{
    			left = mid + 1;
    		}
    	}
    
    	return -1;
        }
    };

Log in to reply
 

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