Day 88, ##, Find Minimum in Rotated Sorted Array, Find Minimum in Rotated Sorted Array II

Find Minimum in Rotated Sorted Array

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.
---------------------------------------------------------------
binary search

class Solution {
public:
    int findMin(vector<int> &num) {
        if (num.size() == 1) return num[0];
        if (num[0] < num.back()) return num[0];
        
        int left = 0;
        int right = num.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (num[mid] < num[mid - 1]) {
                return num[mid];
            }
            
            if (num[mid] > num[right]) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
};

Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?

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.
The array may contain duplicates.
--------------------------------------------------------
if num[mid] == num[right], then num[left] must equal to num[mid] as well

class Solution {
public:
    int findMin(vector<int> &num) {
        if (num.size() == 1) return num[0];
        if (num[0] < num.back()) return num[0];
         
        int left = 0;
        int right = num.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (num[mid] < num[mid - 1]) {
                return num[mid];
            }
            if (num[mid] == num[right]) {
                right--;
            }else if (num[mid] > num[right]) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
         
        return num[0];
    }
};