Solution in C++


  • 0
    P
    class Solution 
    {
    public:
    	int search(vector<int>& nums, int target) 
    	{
    		int lo = 0, hi = nums.size() - 1, mid = 0, rot = 0, realMid;
    		// find the smallest.
    		while (lo < hi) 
    		{
    			mid = (lo + hi) / 2;
    			if (nums[mid] > nums[hi]) lo = mid + 1;
    			else hi = mid;
    		}
    		rot = lo;
    		lo = 0; hi = nums.size() - 1;
    		while (lo < hi) 
    		{
    			mid = (lo + hi) / 2;
    			realMid = (mid + rot) % nums.size();
    			if (nums[realMid] < target) lo = mid + 1;
    			else hi = mid;
    		}
    		lo = (lo + rot) % nums.size();
    		if (nums[lo] == target) return lo;
    		else return -1;
    	}
    };

Log in to reply
 

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