Compact and clean C++ solution


  • 123
    C

    Classic binary search problem.

    Looking at subarray with index [start,end]. We can find out that if the first member is less than the last member, there's no rotation in the array. So we could directly return the first element in this subarray.

    If the first element is larger than the last one, then we compute the element in the middle, and compare it with the first element. If value of the element in the middle is larger than the first element, we know the rotation is at the second half of this array. Else, it is in the first half in the array.

    Welcome to put your comments and suggestions.

     int findMin(vector<int> &num) {
            int start=0,end=num.size()-1;
            
            while (start<end) {
                if (num[start]<num[end])
                    return num[start];
                
                int mid = (start+end)/2;
                
                if (num[mid]>=num[start]) {
                    start = mid+1;
                } else {
                    end = mid;
                }
            }
            
            return num[start];
        }
    

    Some corner cases will be discussed here


  • 0
    M
    This post is deleted!

  • 2
    D

    if num is : [2, 1, 6, 5, 4, 3] ????


  • 5
    C

    Your example is not a valid input.

    The problem says "a sorted array is rotated at some pivot". In your example there are more than one pivots. If there are multiple pivots, then the array is totally unsorted, which makes binary search not applicable.


  • 0
    J

    In fact this example is valid, as in descending order.


  • 0
    C

    Strictly speaking you are right...

    But I guess for most coding questions sorted means increasing order, at least it is true for this problem. If both order are accepted we need to add couple times to do the check.


  • 0
    Q

    totally the same with my solution. how surprising!!!


  • 0
    H

    I think you are assuming the array is sorted in increasing order and then rotated. But, it can be sorted in decreasing order and then rotated. so for an array containing elements <1,2,3>, these are all valid inputs.

    <1,2,3>
    <2,3,1>
    <3,1,2>
    <3,2,1> (no rotation but sorted in decreasing order)
    <2,1,3>
    <1,3,2>


  • 2
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    Z

    There is a corner case that you didn't considered: 2,1,2,2,2. (LeetCode might not include this test case)
    So to modify this problem, when num[mid] == num[start], just start++.


  • 0
    C

    You are right. It cannot handle the duplicate case. However, it is enough for this problem. In the problem there is "You may assume no duplicate exists in the array."


  • 3
    T

    I think my C++ code implementing binary search directly is easier to understand.

    int findMin(vector<int> &num) {
        if(num.empty()) return 0;
        int low = 0;
        int high = num.size() - 1;
        int mid;
    
        while(low < high) {
            mid = (low + high)/2;
            if(num[low]>num[mid]) {
                low++;
                high=mid;
            }
            else if(num[mid] > num[high]) {
                low = ++mid; 
            }
            else
                high = mid; 
        }
    
        return num[low];
    }
    

  • 0
    J

    @changhaz I don't think so. Let's try again.


  • 10
    J

    I just want to deal with the descending order as well.

    class Solution {
    public:
        int findMin(vector<int> &num) {
            if (num.size() == 1) return num[0];
            if (num.size() == 2) return min(num[0], num[1]);
            bool isAscending = ((num[0]<num[1])+(num[1]<num[2])+(num[2]<num[0]) > 1);
            int l = 0;
            int r = num.size() - 1;
            while (l != r) {
                int m = l + (r - l) / 2;  // It can avoid overflow.
                if (isAscending) {
                    if (num[l] < num[r]) return num[l];
                    if (num[m] > num[l]) {
                        l = m + 1;
                    } else {
                        l++;
                        r = m;
                    }
                } else {
                    if (num[l] > num[r]) return num[r];
                    if (num[m] < num[l]) {
                        l = m;
                        r--;
                    } else {
                        r = m - 1;
                    }
                }
            }
            return num[l];
        }
    };

  • 0
    H

    FYI

    int findMin(vector<int> &num) {
        int n=num.size();
        if(n==0)return 0;
        int b=0,e=n-1,m;
        while(b<e-1)
        {
            m=(b+e)/2;
            if(num[m]>num[e]) b=m;
            else e=m;
        }
        return num[b]<num[e]?num[b]:num[e];
    }

  • 0
    N

    If the input is decreasing order, your answer is not correct.


  • 0
    N

    Agree with @Nestle.


  • 0
    Y

    if the array is 3 2 1 7 6 5 4,the answer if not right?


  • 0
    U

    //my solution:after the rotate,the minimum is just like the bottom of its neighbour.
    class Solution {
    public:
    int findMin(vector<int> &num) {
    int len = num.size();
    if(len == 1) return num[0];
    for(int i=1;i<(len-1);i++){
    if(num[i]<num[i-1] && num[i]<num[i+1]) return num[i];
    if(i == len-2) return (num[0]>num[len-1]?num[len-1]:num[0]);
    }
    }
    };


  • 0
    W

    We may also think in this way and maybe easier:
    Computing mid element, compare it with the end element. If the value of the middle element is larger, go to second half. Else, go to the first half. Exit till (!start<end)


Log in to reply
 

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