Question

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

这道题最直观的解法并不难，从头到尾遍历数组一次，我们就能找出最小的元素。这种思路的时间复杂度显然是O（n）。但是这个思路没有利用输入的旋转数组的特性，肯定达不到面试官的要求。

我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还注意到最小的元素刚好是这两个子数组的分界线。在排序的数组中我们可以用二分查找法实现O（logn）的查找。本题给出的数组在一定程度上是排序的，因此我们可以试着用二分查找法的思路来寻找这个最小的元素。

和二分查找法一样，我们用两个指针分别指向数组的第一个元素和最后一个元素。按照题目中旋转的规则，第一个元素应该是大于或者等于最后一个元素的（这其实不完全对，还有特例，后面再加以讨论）。

接着我们可以找到数组中间的元素。如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一个指针指向该中间元素，这样可以缩小寻找的范围。移动之后的第一个指针仍然位于前面的递增子数组之中。

同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们可以把第二个指针指向该中间元素，这样也可以缩小寻找的范围。移动之后的第二个指针仍然位于后面的递增子数组之中。

不管是移动第一个指针还是第二个指针，查找范围都会缩小到原来的一半。接下来我们再用更新之后的两个指针，重复做新一轮的查找。

按照上述的思路，第一个指针总是指向前面递增数组的元素，而第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后一个元素，而第二个指针会指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素。这就是循环结束的条件。

以前面的数组{3,4,5,1,2}为例，我们先把第一个指针指向第0个元素，把第二个指针指向第4个元素（如图2.10（a）所示）。位于两个指针中间（在数组中的下标是2）的数字是5，它大于第一个指针指向的数字。因此中间数字5一定位于第一个递增子数组中，并且最小的数字一定位于它的后面。因此我们可以移动第一个指针让它指向数组的中间（图2.10（b）所示）。

此时位于这两个指针中间（在数组中的下标是3）的数字是1，它小于第二个指针指向的数字。因此这个中间数字1一定位于第二个递增字数组中，并且最小的数字一定位于它的前面或者它自己就是最小的数字。因此我们可以移动第二个指针指向两个指针中间的元素即下标为3的元素（如图2.10（c）所示）。

图2.10　在数组{3,4,5,1,2}中查找最小值的过程

注：旋转数组中包含两个递增排序的子数组，有阴影背景的是第二个子数组。（a）把P1指向数组的第一个数字，P2指向数组的最后一个数字。由于P1和P2中间的数字5大于P1指向的数字，中间的数字在第一个子数组中。下一步把P1指向中间的数字。（b）P1和P2中间的数字1小于P2指向的数字，中间的数字在第二个子数组中。下一步把P2指向中间的数字。（c）P1和P2指向两个相邻的数字，则P2指向的是数组中的最小数字。

此时两个指针的距离是1，表明第一个指针已经指向了第一个递增子数组的末尾，而第二个指针指向第二个递增子数组的开头。第二个子数组的第一个数字就是最小的数字，因此第二个指针指向的数字就是我们查找的结果。

基于这个思路，我们可以写出如下代码：

前面我们提到在旋转数组中，由于是把递增排序数组前面的若干个数字搬到数组的后面，因此第一个数字总是大于或者等于最后一个数字。但按照定义还有一个特例：如果把排序数组的前面的0个元素搬到最后面，即排序数组本身，这仍然是数组的一个旋转，我们的代码需要支持这种情况。此时，数组中的第一个数字就是最小的数字，可以直接返回。这就是在上面的代码中，把indexMid初始化为index1的原因。一旦发现数组中第一个数字小于最后一个数字，表明该数组是排序的，就可以直接返回第一个数字了。

上述代码是否就完美了呢？面试官会告诉我们其实不然。他将提示我们再仔细分析下标为index1和index2（index1和index2分别和图中P1和P2相对应）的两个数相同的情况。在前面的代码中，当这两个数相同，并且它们中间的数字（即indexMid指向的数字）也相同时，我们把indexMid赋值给了index1，也就是认为此时最小的数字位于中间数字的后面。是不是一定这样？

我们再来看一个例子。数组{1,0,1,1,1}和数组{1,1,1,0,1}都可以看成是递增排序数组{0,1,1,1,1}的旋转，图2.11分别画出它们由最小数字分隔开的两个子数组。

图2.11　数组{0,1,1,1,1}的两个旋转{1,0,1,1,1}和{1,1,1,0,1}

注：在这两个数组中，第一个数字、最后一个数字和中间数字都是1，我们无法确定中间的数字1属于第一个递增子数组还是属于第二个递增子数组。第二个子数组用灰色背景表示。

在这两种情况中，第一个指针和第二个指针指向的数字都是1，并且两个指针中间的数字也是1，这3个数字相同。在第一种情况中，中间数字（下标为2）位于后面的子数组；在第二种情况中，中间数字（下标为2）位于前面的子数组中。因此，当两个指针指向的数字及它们中间的数字三者相同的时候，我们无法判断中间的数字是位于前面的子数组中还是后面的子数组中，也就无法移动两个指针来缩小查找的范围。此时，我们不得不采用顺序查找的方法。

在把问题分析清楚形成清晰的思路之后，我们就可以把前面的代码修改为：

源代码：

本题完整的源代码详见08_MinNumberInRotatedArray项目。

测试用例：

- 功能测试（输入的数组是升序排序数组的一个旋转，数组中有重复数字或者没有重复数字）。

- 边界值测试（输入的数组是一个升序排序的数组、只包含一个数字的数组）。

- 特殊输入测试（输入NULL指针）。

本题考点：

- 考查对二分查找的理解。本题变换了二分查找的条件，输入的数组不是排序的，而是排序数组的一个旋转。这要求我们对二分查找的过程有深刻的理解。

- 考查沟通学习能力。本题面试官提出了一个新的概念：数组的旋转。我们要在很短时间内学习理解这个新概念。在面试过程中如果面试官提出新的概念，我们可以主动和面试官沟通，多问几个问题把概念弄清楚。

- 考查思维的全面性。排序数组本身是数组旋转的一个特例。另外，我们要考虑到数组中有相同数字的特例。如果不能很好地处理这些特例，就很难写出让面试官满意的完美代码。