题目:
Suppose a sorted array 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.
链接: http://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
6/13/2017
注意:
会有mid就是最小值的情况,所以更新hi的时候要把mid位置包括进去。实际上lo = mid + 1是没有问题的,因为是nums[mid]比nums[hi]大,所以它肯定不是最小值。
找最小点比找一个特定的值容易很多。
1 public class Solution { 2 public int findMin(int[] nums) { 3 if (nums == null || nums.length == 0) { 4 return -1; 5 } 6 int lo = 0, hi = nums.length - 1; 7 while (lo + 1 < hi) { 8 int mid = lo + (hi - lo) / 2; 9 if (nums[mid] < nums[hi]) { 10 hi = mid; 11 } else { 12 lo = mid; 13 } 14 } 15 if (nums[lo] < nums[hi]) { 16 return nums[lo]; 17 } 18 return nums[hi]; 19 } 20 }
更多讨论
https://discuss.leetcode.com/category/161/find-minimum-in-rotated-sorted-array