面试题11：旋转数组的最小数字

zxzhou 2019-10-29 原文

1.题目描述

题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

2.分析边界条件及测试用例

1.常规输入：包含变换过的数组，测试用例为{1，2，3，4，5}；未经过变换的数组（变换0个元素），测试用例为{1，2，3，4，5}；

2.特殊输入：空值数组输入。

3.分析求解

求解思路，对于此问题其目的在于寻找局部有序数组中的最小元素，其形式也即数组搜索，故而采用二分搜索方法进行求解，但此问题要考虑特殊的情况，将二分的边界条件显示出，因而考虑对实例进行分析，

如{5，1，2，3，4}，运用二分搜索首先搜索数字2，由于输入数组是有序数组的一个变换，故而最小元素必然处于分界处，首先将当前元素与其前后元素相比，若存在逆序关系则可直接得出分界位置也即最小元素；其次，当其左右元素符合升序关系，

判断其与首末元素的大小关系，若其小于首元素，表明分界处（最小元素）在该位置之前，若其大于末元素，则表明分界处位于该位置之后，进一步折半搜索范围；当并未满足以上叙述的所有情况，表明该数组完全升序，返回首元素即可。

 1     public static int searchMinNumber(int[] array) {
 2         if (array.length == 0) return -1;
 3         if (array.length == 1) return array[0];
 4         int lo = 0;
 5         int hi = array.length - 1;
 6         while (lo <= hi) {
 7             int mid = (lo + hi) / 2;
 8             if (mid - 1 >= lo && array[mid] < array[mid - 1]) {
 9                 return array[mid];
10             }
11             else if (mid + 1 <= hi && array[mid] > array[mid + 1]) {
12                 return array[mid + 1];
13             } else {
14                 if (array[mid] < array[lo]) {
15                     hi = mid - 1;
16                 } else if (array[mid] > array[hi]) {
17                     lo = mid + 1;
18                 } else {
19                     return array[0];
20                 }
21             }
22         }
23         return -1;
24     }