-
Notifications
You must be signed in to change notification settings - Fork 1.3k
/
find_min_rotated.cpp
40 lines (36 loc) · 805 Bytes
/
find_min_rotated.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* 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.
*/
#include <iostream>
#include <vector>
int findMin(std::vector<int>& nums) {
int n = nums.size();
if ( n == 1 ) {
return nums[0];
}
if ( n == 2 ) {
return ( nums[0] < nums[1] ? nums[0] : nums[1]);
}
int i = n - 1;
while ( i > 0 && nums[i] > nums[i-1]) {
--i;
}
return nums[i];
}
int main() {
std::cout << "Vec:";
std::vector<int> vec{ 4, 5, 6, 7, 0, 1, 2 };
for ( auto v : vec ) {
std::cout << v << " ";
}
std::cout << std::endl;
std::cout << "Min in above vector: " << findMin(vec) << std::endl;
return 0;
}