# 153.Find-Minimum-in-Rotated-Sorted-Array

## 题目地址

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

## 题目描述

``````Suppose a sorted array 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.

Example
Example 1:

Input：[4, 5, 6, 7, 0, 1, 2]
Output：0
Explanation：
The minimum value in an array is 0.
Example 2:

Input：[2,1]
Output：1
Explanation：
The minimum value in an array is 1.``````

## 代码

Approach #1 Binary Search

``````public class Solution {
public int findMin(int[] nums) {
if (nums.length == 1) return nums[0];

int left = 0, right = nums.length - 1;
if (nmus[right] > nums[0])    return nums[0];

while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid - 1] > nums[mid]) {
return nums[mid];
}

if (nums[mid] > nums[0]) { // 和 nums[0] 比较
left = mid + 1;
} else {
right = mid - 1;
}
}

return -1;
}
}``````

Approach 2:

``````class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0)    return -1;

int start = 0, end = nums.length - 1;
int target = nums[nums.length - 1]; // 和最后一个数字比较

while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] <= target) {
end = min;
} else {
start = mid;
}
}

return Math.min(nums[start], nums[end]);
}
}``````

Last updated