20 lines / c++ solution / 6 ms


  • 1
    P
    class Solution {
    public:
        int findMin(vector<int> &num) {
            return helper(num, 0, num.size()-1, num.size());
        }
        
        int helper(vector<int>& a, int l, int h, int n) {
            int m = (l+h)/2;
            if ((m==0 || a[m-1] > a[m]) && (m==n-1 || a[m+1] > a[m])) {
                return a[m];
            }
            
            if (a[m] < a[h]) {
                return helper(a,l,m-1,n);
            } else {
                return helper(a,m+1,h,n);
            }
        }
    };

  • 0
    X

    Your solution works perfectly when the array is an ascending array (Does the problem itself implicate that the array is an ascending array? ). But when the given array is a descending array, it fails to work out. Consider the test case of [5, 4, 3, 2, 1, 7, 6]. It doesn't even give any answer when this test case is given.
    The following is my solution. 8 ms is needed.

    class Solution
    {
    public:
    	int findMin(vector<int> &num)
    	{
    		int low = 0;
    		int high = num.size() - 1;
    		while(high - low >= 2)
    		{
    			int mid = (low + high)/2;
    			if(num[mid] < num[mid - 1] && num[mid] < num[mid + 1])
    				return num[mid];
    			else if(num[mid] > num[mid - 1] && num[mid] > num[mid + 1])
    				return (num[mid - 1] < num[mid + 1]) ? num[mid - 1] : num[mid + 1];
    			else if(num[mid - 1] < num[mid] && num[mid] < num[mid + 1])
    			{
    				if(num[mid] < num[high]) high = mid;
    				else low = mid;
    			}
    			else
    			{
    				if(num[mid] < num[low]) low = mid;
    				else high = mid;
    			}
    		} 
    		int min = INT_MAX;
    		for(int i = low; i <= high; ++i)
    		{
    			if(num[i] < min) min = num[i];
    		}
    		return min;
    	}
    };
    

  • 0
    P

    It is already given that the array is sorted. I assumed that it is sorted in ascending order.


Log in to reply
 

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