154. Find Minimum in Rotated Sorted Array II - cocoder39/coco39_LC GitHub Wiki

154. Find Minimum in Rotated Sorted Array II

when mid is equal to pivot, we are not sure which side mid is within the range. Thus, we reduce the searching range by one.

compare with nums[end] rather than nums[start]!!! as have discussed in binary search bug, start may equal to mid while end is always different from mid. Thus we cannot start++ when nums[mid] == nums[start], because mid may be start, we may loss the only nums[mid] with start++. Since end is not same as 'mid', if 'nums[mid] == nums[end]', there has to be at least 2 number whose value is equal to nums[end], thus we can use 'end--'

because of duplication, the worst case is O(n), where all elements are equal.

int findMin(vector<int>& nums) {
        int start = 0, end = nums.size() - 1;
        while (start < end) {
            int mid = start + (end - start) / 2; //mid may == start
            if (nums[mid] > nums[end]) {
                start = mid + 1;
            }
            else if (nums[mid] < nums[end]) {
                end = mid;
            }
            else { //not sure which side mid is
                end--; //dumplicate nums[end] can be ignored
            }
        }
        return nums[start];
    }