Sharing my solution,using binary idea to search,O(logn)


  • 1
    N

    1.try to find num[ low - high] is sorted or not,if it is sorted ,return num[low]

    2.if num[low - mid] is sorted,minimum must in mid+1 ~ high.

    3.i think minimum number is in unsorted part.

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

Log in to reply
 

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