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

+ A[mid] > A[start]，那么最小值一定在右半区间，譬如[4,5,6,7,0,1,2]，中间元素为7，7 > 4，最小元素一定在[7,0,1,2]这边，于是我们继续在这个区间查找。
+ A[mid] < A[start]，那么最小值一定在左半区间，譬如[7,0,1,2,4,5,6]，这件元素为2，2 < 7，我们继续在[7,0,1,2]这个区间查找。

```c++
class Solution {
public:
int findMin(vector &num) {
int size = num.size();

if(size == 0) {
return 0;
} else if(size == 1) {
return num[0];
} else if(size == 2) {
return min(num[0], num[1]);
}

int start = 0;
int stop = size - 1;

while(start < stop - 1) {
if(num[start] < num[stop]) {
return num[start];
}

int mid = start + (stop - start) / 2;
if(num[mid] > num[start]) {
start = mid;
} else if(num[mid] < num[start]) {
stop = mid;
}
}

return min(num[start], num[stop]);
}
};
```

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

> The array may contain duplicates.

+ A[mid] > A[start]，右半区间查找。
+ A[mid] < A[start]，左半区间查找。
+ A[mid] = A[start]，出现这种情况，我们跳过start，重新查找，譬如[2,2,2,1]，A[mid] = A[start]都为2，这时候我们跳过start，使用[2,2,1]继续查找。

```c++
class Solution {
public:
int findMin(vector &num) {
int size = num.size();

if(size == 0) {
return 0;
} else if(size == 1) {
return num[0];
} else if(size == 2) {
return min(num[0], num[1]);
}

int start = 0;
int stop = size - 1;

while(start < stop - 1) {
if(num[start] < num[stop]) {
return num[start];
}

int mid = start + (stop - start) / 2;
if(num[mid] > num[start]) {
start = mid;
} else if(num[mid] < num[start]) {
stop = mid;
} else {
start++;
}
}

return min(num[start], num[stop]);
}
};
```