[leetcode] Find Minimum in Rotated Sorted Array

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.

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.