My pretty simple code to solve it


  • 191
    S
    class Solution {
    public:
        int findMin(vector<int> &num) {
            int lo = 0;
            int hi = num.size() - 1;
            int mid = 0;
            
            while(lo < hi) {
                mid = lo + (hi - lo) / 2;
                
                if (num[mid] > num[hi]) {
                    lo = mid + 1;
                }
                else if (num[mid] < num[hi]) {
                    hi = mid;
                }
                else { // when num[mid] and num[hi] are same
                    hi--;
                }
            }
            return num[lo];
        }
    };
    

    When num[mid] == num[hi], we couldn't sure the position of minimum in mid's left or right, so just let upper bound reduce one.


  • 91
    E

    a simple question: why mid = lo + (hi - lo) / 2 rather than mid = (hi + lo) / 2 ?


  • 60
    S

    This is a famous bug in binary search. if the size of array are too large, equal or larger than the upper bound of int type, hi + lo may cause an overflow and become a negative number. It's ok to write (hi + lo) / 2 here, leetcode will not give you a very large array to test. But we'd better know this. For a detailed information or history of this bug, you could search "binary search bug" on google.


  • 0
    E

    that makes sense, I'll google it, thank you!


  • 2
    X

    This method would be even slower than just loop through all the numbers btw hi and lo to check if they are all the same.


  • 0
    S

    I think in worst case no solution is better than O(n) complexity.


  • 1
    N

    Could you please explain the reason of hi-- more carefully?


  • 0
    Q

    very concise and smart idea


  • 0
    D

    thanks very much~


  • 0
    J

    Thanks a lot for your answer.


  • 0
    T

    Thanks for your answer!


  • 2

    I suggest another golfing code using bit manipulation: mid = (lo & hi) + ((lo ^ hi) >> 1): the first part accounts for the carry bit and the second part accounts for the sum bit. Since we need to divide by 2, so the sum bit shifts to right by 1 and the carry bit simply does not shift (originally it needs to shift to left by 1).


  • 4

    Hi, namedfree. If you want to know how hi-- works, I suggest you to run the above codes on the two examples [1, 0, 1, 1, 1] and [1, 1, 1, 0, 1] on the solution tag.


  • 0
    N

    3Q,I have understood.


  • 5
    S

    I am confused on using

    • while (lo < hi) ... hi = mid;
    • while (lo <= hi) ... hi = mid-1;

    in which case use each?


  • 14
    B

    This code is correct to return the minimum value of the array. But in terms of "find the minimum value index" it is not right.
    Consider this case: 1 1 1 1 1 1 1 1 2 1 1
    the min index returned is 0, while actually it should be 9.
    For this case: 2 2 2 2 2 2 2 2 1 2 2
    it will return the correct index, which is 8.

    The reason is, the pivot index will be passed by at hi--. To avoid this, we can add the following judgement:

    else {

    if (nums[hi - 1] > nums[hi]) {
        lo = hi;
        break;
    }
    hi--;
    

    }


  • 1

    Hi, benlong. Why do you say in cases [1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1] we should return 9? I think it is Ok to return the first index of the minimum, which is just 0. Moreover, where do you get this 9: the 9-the element is neither the first minimum nor the last minimum...


  • 8
    B

    Hi jiaochao,

    I didn't say this approach is wrong. To solve this particular problem it's absolutely correct and enough.

    What I was trying to say, however, is that it would be better if we can return exactly the 1st minimum value index, which is 9 in this case. The significance of this index lies in that it is also the number of shifts we have done to rotate the original normal sequence [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2] to the non-sorted form. That is to say, 9 is the offset of all elements from their normal positions.

    With this offset, we can easily solve the other closely related problem [Search in Rotated Sorted Array II] with unified one pass binary search:

        //hi is the offset we found in previous step, omitted here;
        int offset = hi;
        lo = 0;
        hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            //please note the mapping from logical mid to realMid in rotated array
            int realMid = (mid + offset) % n;
            if (nums[realMid] == target) {
                return true;
            } else if (nums[realMid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        
        return false;

  • 0
    This post is deleted!

  • 4

    Love the phrases "3Q, I have understood." and "we couldn't sure".


Log in to reply
 

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