Accepted C++ solution with reasoning


  • 0
    E

    The problem falls into identifying the section with monotonically ascending array. If it is found, then the left element is naturally the minimum (Assuming sorted array is ascending array, not descending one).

    So, what is a monotonically ascending array? Simply num[left] <= num[mid] <= num[right]. You can actually ignore num[mid] here.

    There are 4 possibilities for the combinations with a mid-point selection:

    1. num[left] <= num[mid] && num[mid] <= num[right] ==> you found it!
    2. num[left] <= num[mid] && num[mid] > num[right] ==> pivot on the right, left=mid+1
    3. num[left] > num[mid] && num[mid] <= num[right] ==> pivot on the left, right=mid (NOT right=mid+1, since mid-point could be the pivot
    4. num[left] > num[mid] && num[mid] > num[right] ==> IMPOSSIBLE! (assume ascending sorted array)

    Use the binary search framework, the code can be organized as below:

    int findMin(vector<int> &num) {
        int left = 0;
        int right = num.size() - 1;
    
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
    
            if (num[left] <= num[mid] && num[mid] <= num[right])
            {
                // is a sorted array 
                break;
            }
    
             // judge where pivot is
            if (num[mid] < num[left])
            {
                // pivot is on the left
                right = mid;
            }
            else if (num[mid] > num[right])
            {
                // pivot is on the right
                left = mid + 1;
            }
        }
        
        return num[left];
    }

Log in to reply
 

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