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.

Hide Tags

Array Binary Search

Show Similar Problems

Force solution, o(n) AC

//will it contains negatives?
//Could the array not rotated? Just an ordinary sorted array?
//What's the complexity requirements? O(n^2) O(logn)?

//Does sorted array means increasing array? 
//Can I manipulate the input?
class Solution {
public:
    int findMin(vector<int>& nums) {
        int min = nums[0];
        for(int i = 0; i < nums.size(); i++){
            min = min < nums[i] ? min: nums[i];
        }
        return min;
    }
};

Binary search o(logn)

//will it contains negatives?
//Could the array not rotated? Just an ordinary sorted array?
//What's the complexity requirements? O(n^2) O(logn)?

//Does sorted array means increasing array? 
//Can I manipulate the input?
class Solution {
public:
    int findMin(vector<int>& nums) {
        //suppose the nums.size() > 0
        //extreme cases
        if(nums.size() == 1) return nums[0];

        return _findMin(nums, 0, nums.size());
    }
    //[start, end)
    int _findMin(vector<int>& nums, int start, int end){
        //base condition
        if(end - start == 1){
            return nums[start];
        }
        //pivot is not between start and end
        if (nums[start] < nums[end - 1]) return nums[start];
        //ordinary condition
        int mid = (start + end) / 2;
        if(nums[mid] > nums[start]){
            return _findMin(nums, mid + 1, end);
        }
        else{
            return _findMin(nums, start + 1, mid + 1);//be careful!
        }
    }
};