Fastest C++ Solution without unnecessary search (7ms)


  • -1
    E
     class Solution {
        public:
            int findMin(vector<int> &num) {
                int low = 0, high = num.size() - 1;
                return BinarySearch(num, low, high);
            }
            int BinarySearch(vector<int> &num, int low, int high) {
                if(high - low <= 0) return num[0];
                else {
                    int mid = (low + high) / 2;
                    if(num[mid] < num[mid - 1]) return num[mid];
                    else if(num[mid] > num[mid + 1]) return num[mid + 1];
                    else if(num[mid] < num[high]) return BinarySearch(num, low, mid);
                    else if(num[mid] > num[high]) return BinarySearch(num, mid, high);
                }
            }
        };
    

    returns as long as we hit the pivot(either at left or at right neighbors), so we don't need to divide into smallest pieces.


  • 0
    N

    This solution is wrong. Try test case {0,1,2,7}


  • 0
    E

    I don't think the test case {0 1 2 7} is wrong. Please check it again.


  • 0
    N

    try it yourself in VS, you can find it. “mid” can be 0,then num[mid-1]?


Log in to reply
 

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