4ms C++ binary search solution with short explanation


  • 0
    D

    The idea is to binary search for the minimum. If the midpoint of an interval is larger than the right endpoint, the minimum must be in the right half of the interval. If not, the minimum is in the left half, but may be the midpoint itself (so we keep the midpoint in the active search interval in this case).

    class Solution {
    public:
        int findMin(vector<int> &num) {
            int L = 0, U = num.size() - 1;
            while (L < U) {
                int M = L + (U - L) / 2;
                if (num[M] > num[U]) {
                    L = M + 1;
                } else {
                    U = M;
                }
            }
            return num[L];
        }
    };

Log in to reply
 

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