153.find-minimum-in-rotated-sorted-array.cpp

/*
 * @lc app=leetcode id=153 lang=cpp
 *
 * [153] Find Minimum in Rotated Sorted Array
 *
 * https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
 *
 * algorithms
 * Medium (42.49%)
 * Total Accepted:    261.5K
 * Total Submissions: 615.5K
 * Testcase Example:  '[3,4,5,1,2]'
 *
 * Suppose an array sorted in ascending order 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.
 *
 * Example 1:
 *
 *
 * Input: [3,4,5,1,2]
 * Output: 1
 *
 *
 * Example 2:
 *
 *
 * Input: [4,5,6,7,0,1,2]
 * Output: 0
 *
 *
 */
#include <vector>
using namespace std;

class Solution
{
  public:
    int findMin(vector<int> &nums)
    {
        if (nums.size() == 0)
            return -1;

        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            // Prevent (left + right) overflow
            int mid = left + (right - left) / 2;

            if (nums[mid] < nums[right])
                right = mid;
            else
                left = mid + 1;
        }
        return nums[left];
    }
};