153. Find Minimum in Rotated Sorted Array

Leetcode Array Binary Search

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

分析

在一个有序数组中查找一个元素可以用二分查找，二分查找也称为折半查找，每次都能将查找区间减半，这种折半特性的算法时间复杂度都为$O(\log N)$。

本题可以修改二分查找算法进行求解：

• 当nums$[mid]$ <= nums$[hi]$ 的情况下，说明解在$[lo, mid]$之间，此时令$hi = mid$；
• 否则解在$[mid + 1, hi]$之间，令$lo = mid + 1$。

public int findMin(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int lo = 0, hi = nums.length - 1, mid;
    while (lo < hi){
          mid = (lo + hi)/2;
          if(nums[mid] <= nums[hi]) hi = mid;
          else lo = mid + 1;
    }
    return nums[lo];
}