## 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.

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! } } };