剑指offer,旋转数组的最小值题解
旋转数组的最小数字
http://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba
旋转数组题解
题目描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
思路:二分法
分以下几种情况讨论
(1) array[low] < array[high],此时数组必定未旋转,返回array[low]
(2) array[low] == array[high],此时情况很复杂,不如将high--,再进行比较
(3) 经过(1),(2)的筛选,此时 array[low] > array[high],当array[mid] >= array[low],最小值必定在右边,令low = mid + 1
(4) 最小值在左边或者中间时,令high = mid
代码如下
import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { if (array == null || array.length == 0) return 0; int low = 0, high = array.length - 1; while (low < high) { int mid = low + (high - low) / 2; if (array[low] < array[high]) { return array[low]; }else if (array[low] == array[high]) { high--; }else if (array[mid] >= array[low]) { low = mid + 1; }else { high = mid; } } return array[low]; } }