|
1 | 1 | /* |
2 | | - Given sorted array after some rotation, find min value |
3 | | - Ex. nums = [3,4,5,1,2] -> 1, nums = [4,5,6,7,0,1,2] -> 0 |
| 2 | + * @lc app=leetcode id=153 lang=cpp |
| 3 | + * |
| 4 | + * [153] Find Minimum in Rotated Sorted Array |
| 5 | +*/ |
4 | 6 |
|
5 | | - Binary search + ensuring we never disqualify possible min value |
| 7 | +// @lc code=start |
| 8 | +classSolution |
| 9 | +{ |
| 10 | +public: |
| 11 | +intfindMin(vector<int> &nums) |
| 12 | + { |
| 13 | +// Neetcode solution Ologn time O1 space binary search |
| 14 | +int res = nums[0]; |
| 15 | +int l =0; |
| 16 | +int r = nums.size() -1; |
6 | 17 |
|
7 | | - Time: O(log n) |
8 | | - Space: O(1) |
9 | | -*/ |
| 18 | +while (l <= r) |
| 19 | + { |
| 20 | +if (nums[l] < nums[r]) |
| 21 | + { |
| 22 | + res =min(res, nums[l]); |
| 23 | +break; |
| 24 | + } |
| 25 | +int mid = l + (r - l) /2; |
| 26 | + res =min(res, nums[mid]); |
10 | 27 |
|
11 | | -classSolution { |
12 | | -public: |
13 | | -intfindMin(vector<int>& nums) { |
14 | | -int low =0; |
15 | | -int high = nums.size() -1; |
16 | | - |
17 | | -// not low <= high since not searching for target |
18 | | -while (low < high) { |
19 | | -int mid = low + (high - low) /2; |
20 | | -// ex. [3,4,5,6,7,8,9,1,2], mid = 4, high = 8 |
21 | | -// nums[mid] > nums[high], min must be right |
22 | | -if (nums[mid] > nums[high]) { |
23 | | -// never consider mid bc know for sure not min |
24 | | - low = mid +1; |
25 | | -// ex. [8,9,1,2,3,4,5,6,7], mid = 4, high = 8 |
26 | | -// nums[mid] <= nums[right], min must be left |
27 | | - }else { |
28 | | -// consider mid still bc could be min |
29 | | - high = mid; |
| 28 | +if (nums[mid] >= nums[l])// mid present in left sorted array |
| 29 | + { |
| 30 | + l = mid +1;// try to move closer to right sorted array |
| 31 | + } |
| 32 | +else |
| 33 | + { |
| 34 | + r = mid -1; |
30 | 35 | } |
31 | 36 | } |
32 | | - |
33 | | -// low lands on correct value, never disqualified mins |
34 | | -return nums[low]; |
| 37 | + |
| 38 | +return res; |
35 | 39 | } |
36 | 40 | }; |
| 41 | +// @lc code=end |