153/154 Find Minimum in Rotated Sorted Array I/ II

153 / Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

154 / The array may contain duplicates.

why mid = lo + (hi - lo) / 2 rather than mid = (hi + lo) / 2 ?

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.

154 / ```class Solution { public: int findMin(vector &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.```