Python程序员面试算法宝典：旋转数组最小元素查找

【出自YMX面试题】

难度系数：★★★☆☆ 被考察系数：★★★★☆

题目描述：

把一个有序数组最开始的若干个元素搬到数组的末尾，称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组[3，4，5，1，2]为数组[1，2，3，4，5]的一个旋转，该数组的最小值为1。

分析与解答：

Python中可以使用列表来表示有序数组，因此示例中都用列表来表示有序数组。

其实这是一个非常基本和常用的数组操作，它的描述如下：

有一个数组X[0...n-1]，现在把它分为两个子数组：x1[0...m]和x2[m+1...n-1]，交换这两个子数组，使数组x由x1x2变成x2x1，例如x=[1，2，3，4，5，6，7，8，9]，x1=[1，2，3，4，5]，x2=[6，7，8，9]，交换后，x=[6，7，8，9，1，2，3，4，5]。

对于本题的解决方案，最容易想到的，也是最简单的方法就是直接遍历法。但是这种方法显然没有用到题目中旋转数组的特性，因此，它的效率比较低下，下面介绍一种比较高效的二分查找法。

通过数组的特性可以发现，数组元素首先是递增的，然后突然下降到最小值，然后再递增。虽然如此，但是还有下面三种特殊情况需要注意：

（1）数组本身是没有发生过旋转的，是一个有序的数组，例如序列[1，2，3，4，5，6]。

（2）数组中元素值全部相等，例如序列[1，1，1，1，1，1]。

（3）数组中元素值大部分都相等，例如序列[1，0，1，1，1，1]。

通过旋转数组的定义可知，经过旋转之后的数组实际上可以划分为两个有序的子数组，前面的子数组的元素值都大于或者等于后面子数组的元素值。可以根据数组元素的这个特点，采用二分查找的思想不断缩小查找范围，最终找出问题的解决方案，具体实现思路如下所示：

按照二分查找的思想，给定数组arr，首先定义两个变量low和high，分别表示数组的第一个元素和最后一个元素的下标。按照题目中对旋转规则的定义，第一个元素应该是大于或者等于最后一个元素的（当旋转个数为0，即没有旋转的时候，要单独处理，直接返回数组第一个元素）。接着遍历数组中间的元素arr[mid]，其中mid=（high+low）/2。

（1）如果arr[mid]＜arr[mid-1]，则arr[mid]一定是最小值；

（2）如果arr[mid+1]＜arr[mid]，则arr[mid+1]一定是最小值；

（3）如果arr[high]＞arr[mid]，则最小值一定在数组左半部分；(www.xing528.com)

（4）如果arr[mid]＞arr[low]，则最小值一定在数组右半部分；

（5）如果arr[low]==arr[mid]且arr[high]==arr[mid]，则此时无法区分最小值是在数组的左半部分还是右半部分（例如：[2，2，2，2，1，2]，[2，1，2，2，2，2，2]）。在这种情况下，只能分别在数组的左右两部分找最小值minL与minR，最后求出minL与minR的最小值。

示例代码如下：

程序的运行结果为：

1

0

算法性能分析：

一般而言，二分查找的时间复杂度为O（log₂^N），对于这道题而言，大部分情况下时间复杂度为O（log₂^N），只有每次都满足第（5）条的时候才需要对数组中所有元素都进行遍历，因此，这种方法在最坏的情况下的时间复杂度为O（N）。

引申：如何实现旋转数组功能？

分析与解答：

先分别把两个子数组的内容交换，然后把整个数组的内容交换，即可得到问题的解。

以数组x1[1，2，3，4，5]与数组x2[6，7，8，9]为例，交换两个数组后，x1=[5，4，3，2，1]，x2=[9，8，7，6]，即x=[5，4，3，2，1，9，8，7，6]。交换整个数组后，x=[6，7，8，9，1，2，3，4，5]。

示例代码如下：

程序的运行结果为：

4 5 1 2 3

算法性能分析：

由于这种方法需要遍历两次数组，因此，它的时间复杂度为O（N）。而交换两个变量的值，只需要使用一个辅助储存空间，所以，它的空间复杂度为O（1）。