153. Find Minimum in Rotated Sorted Array

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.

Example 1:

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

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

Solution

本题可以用Binary Search解决: 如果数组部分有序,由lo, mid, hi可以将数组分成两块,必定有一块是无序的,有一块是有序的,我们要做的就是一直缩小无序序列的宽度,直至找到最小值。

关于Binary Search脑海中要有模板,注意点如下:

  1. while(lo < hi) 注意什么时候用等号,什么时候不用等号
  2. nums[lo] < nums[hi],表示lo - hi之间有序
  3. lo = mid + 1, lo指针一定要移动,因为lo可能和mid同值而引起死循环
  4. hi = mid, hi 必定与mid 值不同,除非lo == hi

Complex

O(logN) O(1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
public int findMin(int[] nums) {
int lo = 0, hi = nums.length -1;
while(lo < hi){
if(nums[lo] < nums[hi]) return nums[lo];
int mid = (lo + hi) / 2;
if(nums[lo] <= nums[mid]){
lo = mid + 1;
}else{
hi = mid;
}
}
return nums[lo];
}