Solution in C++, well-explained


  • 4

    Solution

    In a rotate array, there will be a position where the sequence changes, no longer ascending and that number will be the minimum we are searching for. Accordingly, we can adopt binary searching to find it out and the key will be that sequence change. Let's suppose l and r will be the start and the end of the array and m is the middle between them.

    • First, if nums[m] > nums[r] then the sequence change number will be between m and r.
    • Second, if nums[m] < nums[r], then the sequence change number will be between l and m.
    • Third, if there exist duplicates and result in nums[m]==nums[r] then we will not know that that sequence change number but one thing for sure, nums[r] will not be the minimum so we can just move the r backward to eliminate nums[r] by r--, which can then be able to terminate the searching properly.

    The third part is the essential, which delicately handle the duplicates and terminate the searching elegantly.

    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int l = 0, r = nums.size()-1;
            while(l < r){
                int m = l+((r-l)>>1);
                if(nums[m] < nums[r]) r = m;
                else if(nums[m] > nums[r]) l = m+1;
                else r--;
            }
            return nums[l];
        }
    };
    

    Always welcome new ideas and practical tricks, just leave them in the comments!


  • 0
    J

    Just curious about why using l+((r-l)>>1) instead of (l + r) >> 1 improves the speed ?! :P


  • 0

    @JackCen Shifting has lower precedence compared to +, which will result in bad calculation sequence.


  • 0
    R

    @JackCen l + r may overflow in some cases


  • 1
    A

    @LHearen said in Solution in C++, well-explained:

            int m = l+((r-l)>>1);
            else if(nums[m] < nums[r]) r = m;
            else if(nums[m] > nums[l]) l = m+1;
            else r--;
    

    This solution is actually wrong.
    Firstly, there is no if but else.
    Secondly, even if we fix the above error, it still fails simple testcases.
    e.g.

    Run Code Result:
    Your input
    [1,3,3,3]
    
    Your answer
    3
    
    Expected answer
    1 
    

    It is not hard to find where it is wrong, but I'll leave it to yourself.


  • 0

    @ayuanx Sorry about the wrong typing since updated last time. But I am very curious about it that do you actually read the explanation before the code? It's clearly demonstrated that the method is alright and now of course, thank you for testing it again and I update it now for the correct version.


  • 0
    A

    @LHearen That's because you secretly changed the following line. It was l in your original version. Don't presume that I wouldn't notice. There is hard evidence in my last post. But you are right that I didn't read your explanation before your code, as the ability to read code directly should be a basic skill of any coder.

    else if(nums[m] > nums[r]) l = m+1;


  • 0

    @ayuanx As Google's cache shows, the version in the explanation had already correctly used r.


  • 0
    A

    @StefanPochmann Yeah, but like I said, I didn't read the description at all. I only read code itself.


  • 0

    @ayuanx I just don't get the "secretly changed" and "presume that I wouldn't notice". He did acknowledge the wrong typing and did say that he corrected it, didn't he? And as the cache shows, it really was just a typo in the code, so I don't understand the fuss.


  • 0
    A

    @StefanPochmann Never mind, it all started because I didn't read the description but code. So when he said his solution was correct e.g. "It's clearly demonstrated that the method is alright", I thought he meant his code and code only.


  • 0
    W

    Hi , @LHearen and guys, thanks for sharing the code and it works. My confusion on this question and many other questions is, for this specific question, why in the code we need to use the nums[r] element as the benchmark to compare to. I tried to use the nums[l] element as the benchmark but I failed.

    Furthermore, I think I still have a lot of uncertain points on binary search, there are many variations in a simple binary search. For example,

    • in the condition test part, when to use l < r or l <=r,
    • in the while body, when to use two branches (if > and else) or three branches (if >, = and else).
    • when move the cursor, how to move the cursor, e.g. lo = mid + 1 or lo = mid
    • (this is the newest point I learnt from this post) which element to compare nums[mid] with, nums[l] or nums[r]

    It will be perfect if anyone can give a summarization on these issues or a link to an article is also fine. Any other comments are also appreciated.


  • 0
    E

    @wondershow

    you can compare against nums[l] but this requires an extra comparison between nums[l] and nums[r] to see if our current window still contains the rotated part. For instance if the array is not rotated at all (or after the last point which will also lead to no change), if we just do a comparison against l, we can't possible tell whether we should move left or right. Doing a comparison against nums[r] lets us handle both when we have the rotated part in our spectrum and when we do not. You might be confused because only doing a comparison against nums[r] will lead to the wrong result if we're completely in the rotated section, but If you think about it carefully, we won't ever be in that situation due to the way we're adjusting our pointers.


Log in to reply
 

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