Share my C++ solution for both ascending and descending orders. O(logN)~O(N) time complexity


  • 0
    J

    I haven't found any effective non-recursive solution for the same purpose.

    class Solution {
    public:
        int findMin(vector<int> &num) {
            return binarySearch(num, 0, num.size());
        }
        int binarySearch(vector<int> &num, int begin, int end) {
            if (end - begin < 1) return num[0];
            int mid = begin + (end - begin) / 2;
            if ((mid-1 < begin || num[mid-1] > num[mid]) &&
                    (mid+1 >= end || num[mid] < num[mid+1])) {
                return num[mid];
            }
            int lmin = binarySearch(num, begin, mid);
            int rmin = binarySearch(num, mid + 1, end);
            return min(lmin, rmin);
        }
    };
    

    The official solution is O(1)~O(N) for the ascending/descending order, but there is no easy way to detect the order.


Log in to reply
 

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