# LeetCode-153 Find Minimum in Rotated Sorted Array

Title Description

Suppose an array sorted in ascending order 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.

The main idea of the topic

An original ordered array is scrambled once, that is, it is divided into two subarrays from one position in the array, and the positions of the two subarrays are interchanged (but the arrangement in the subarray is still maintained), and the smallest number in the disordered array is found.

Example

E1

```Input: [3,4,5,1,2]
Output: 1```

E2

```Input: [4,5,6,7,0,1,2]
Output: 0```

Solving problems

Based on the improvement of binary search, it is necessary to determine the position of mid (i.e. in the smaller subarray after exchange or in the larger subarray) when binary search is used to query the number direction.

Complexity analysis

Time complexity: O(log(n))

Space complexity: O(1)

Code

```class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();

return solve(nums, 0, n - 1, n);
}
//Two points search
int solve(vector<int>& nums, int low, int high, int n) {
if(low == high)
return nums[low];
int mid = (low + high) / 2;
// If two boundary pointers are adjacent, it means that the minimum value must be in it, and return the minimum value;
if(abs(low - high) == 1)
return min(nums[low], nums[high]);
//judge mid Specific location of
if(mid > 0 && mid < n - 1)
if(nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1])
return nums[mid];
else {
//mid Is in a large subarray
if(nums[mid] > nums[low] && nums[mid] > nums[high])
return solve(nums, mid + 1, high, n);
//low，mid，high In an ordered array, return low that will do
else if(nums[mid] > nums[low])
return nums[low];
//mid In smaller subarrays
else
return solve(nums, low, mid, n);
}
//mid Under the boundary condition, the minimum value must be nearby
else if(mid > 0)
return min(nums[mid], nums[mid - 1]);
else
return min(nums[mid], nums[mid + 1]);
}
};```

Tags: PHP

Posted on Sun, 03 Nov 2019 12:40:48 -0800 by Hallic7