2.Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element. You may assume no duplicate exists in the array.

Example 1:
Input: [3,4,5,1,2] 
Output: 1

Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0 

Solution:

class Solution
{
public:
    int findMin(vector<int> &nums)
    {

        int start = 0;
        int end = nums.size()-1;
        int res = 0;
        while (start < end)
        {
            int mid = (start + end) / 2;

            if (nums[mid] > nums[mid + 1])
            {
                res = mid + 1;
                break;
            }
            else if (nums[mid]>nums[end])
            {
                start = mid+1;
            }
            else
            {
                end = mid;
            }
        
        }
        return nums[res];
    }
};

This is an optimized solution using binary search O(log n) time. Another implementation can be using linear search which requires O(n) time.

Type II:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element. The array may contain duplicates.

Solution:

Using duplicates with the above solution will take O(n) time.

The below solution takes O(log n) time.

class Solution
{
public:
    int findMin(vector<int> &nums)
    {

        int start = 0;
        int end = nums.size()-1;
        int res = 0;
        while (start < end)
        {
            int mid = (start + end) / 2;

            if (nums[mid] > nums[mid + 1])
            {
                res = mid + 1;
                break;
            }
            else if (nums[mid]>nums[end])
            {
                start = mid+1;
            }
            else
            {
                end = mid;
            }
        
        }
        return nums[res];
    }
};