154. FindMinimuminRotatedSortedArrayII

Description:

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/#/description

Algorithm:

1. Same with 153. FindMinimuminRotatedSortedArray
2. Use squeeze from left and right to find result;

Code1:

class Solution {
public:
int findMin(vector<int>& nums) {
int minEle = INT_MIN;
for (int i = 0; i < nums.size() – 1;i++)
{
if (nums[i + 1] < nums[i])
minEle = nums[i + 1];
}
if (minEle == INT_MIN)
minEle = nums[0];
return minEle;
}
};

Code2:
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0;
int r = nums.size() – 1;

while (l < r) {
int m = l + ((r – l) >> 1);

if (nums[m] < nums[r]) {
r = m;
}
else if (nums[m] > nums[r]) {
l = m + 1;
}
else {
–r;
}
}

return nums[l];
}
};

Timing & Space:

O(n) / O(logn) & O(1)