4ms simple C++ code with explanation


  • 40
    J

    In this problem, we have only three cases.

    Case 1. The leftmost value is less than the rightmost value in the list: This means that the list is not rotated.
    e.g> [1 2 3 4 5 6 7 ]

    Case 2. The value in the middle of the list is greater than the leftmost and rightmost values in the list.
    e.g> [ 4 5 6 7 0 1 2 3 ]

    Case 3. The value in the middle of the list is less than the leftmost and rightmost values in the list.
    e.g> [ 5 6 7 0 1 2 3 4 ]

    As you see in the examples above, if we have case 1, we just return the leftmost value in the list. If we have case 2, we just move to the right side of the list. If we have case 3 we need to move to the left side of the list.

    Following is the code that implements the concept described above.

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

  • 0
    A

    Yes, your code is very trick. I like your code.


  • 0
    A

    very useful usage of binary find


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

  • -1
    Z

    How about this case:[2 1 0 7 6 5 4], I think the result of your code is wrong.
    The array has not to be in ascending order.


  • 0
    J

    If we have to take into consideration the order of decreasing, we need to reverse the input vector. In this problem, it looks like we don't need to care about the decreasing order.


  • 0
    Q

    great solution. thanks for the ++start;


  • 0
    K

    your case is impossible, you can't get an array like that from rotating a sorted array.


  • 0
    L

    @phu1ku could you explain why should we use start = mid+1;???
    I am really confused about this ...thank you


  • 0
    This post is deleted!

  • -1

    said in 4ms simple C++ code with explanation:

    left = mid + 1;

    It is ugly !


  • 0
    J
    This post is deleted!

  • 0
    J
    This post is deleted!

  • 1
    J

    Return twice might be redundant? See the edit on while loop

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

  • 0

    @jaewoo Could you please let us know the complexity of your code? In my opinion, it should be O(logN) since we reduce the search space by half in every iteration. Am I right?


Log in to reply
 

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