Description
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.NoticeYou may assume no duplicate exists in the array.ExampleGiven [4, 5, 6, 7, 0, 1, 2] return 04/24/2017
算法班
不需要跟特定值比较,while里面判断只有2个分支。
1 public class Solution { 2 /** 3 * @param nums: a rotated sorted array 4 * @return: the minimum number in the array 5 */ 6 public int findMin(int[] nums) { 7 // write your code here 8 if (nums == null || nums.length == 0) return -1; 9 int start = 0, end = nums.length - 1;10 11 while (start + 1 < end) {12 int mid = start + (end - start) / 2;13 if (nums[mid] < nums[end]) {14 end = mid;15 } else {16 start = mid;17 }18 }19 return nums[start] < nums[end]? nums[start]: nums[end];20 }21 }