（说明：本文中的题目、题目详细说明及参考代码均摘自 “何海涛《剑指Offer：名企面试官精讲典型编程题》2012年”）
题目把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组 {3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转，该数组的最小值为 1 。
算法设计思想1. 暴力查找（Bruteforce Search）：把旋转数组从前到后遍历一遍，其时间复杂度为 O(n)。很明显，这种思想非常直接粗暴，没有用到旋转数组的性质。
2. 二分查找（Binary Search）：每次查找都把旋转数组平均分成两部分，通过比较当前旋转数组两端点和中间点的值，判断最小值在数组的哪一部分，从而达到缩小搜索范围的目的。其中，两端点为当前的旋转数组索引最小和索引最大的元素，中间点为这两部分子数组的连结元素，也可以看做为轴枢点（pivot point），这里取旋转数组的最小索引和最大索引的算术平均值（向下取整）作为索引，其对应的元素作为中间点。具体过程，如图 2.10 所示。
需要注意，当旋转数组的两端点的值都与中间点的值相等时，因为无法判断最小值在哪一部分，因此需要采用顺序查找方法，即暴力查找。其示例如图 2.11 所示。
#include <stdio.h>
#include <exception>
#include <iostream>
// Declare a parameter exception
class ParamException: public std::exception {
virtual const char* what() const throw()
{
return "Error: input parameters exception!";
}
};
// find minimum in data[staIndex..endIndex]
int findMinInRotatedArray(int data[], int staIndex, int endIndex)
{
if (staIndex > endIndex || data == NULL)
{
throw ParamException();
}
int minimum = data[staIndex];
if (data[staIndex] >= data[endIndex] && staIndex < endIndex - 1) // 易错点
{
// Use Binary Search
int midIndex = (staIndex + endIndex) / 2;
if (data[midIndex] > data[staIndex])
minimum = findMinInRotatedArray(data, midIndex, endIndex);
else if (data[midIndex] < data[endIndex])
minimum = findMinInRotatedArray(data, staIndex, midIndex);
else
{
// Find the minimum sequentially
for (int i = staIndex+1; i <= endIndex; ++i)
if (minimum > data[i])
minimum = data[i];
}
}
else if (staIndex == (endIndex - 1))
{
minimum = data[staIndex] > data[endIndex]? data[endIndex]:data[staIndex];
}
return minimum;
}
void unitest()
{
int arr1[] = {3, 4, 5, 1, 2};
int arr2[] = {1, 0, 1, 1, 1};
int arr3[] = {1, 1, 1, 0, 1};
int arr4[] = {1, 2, 3, 4, 5};
printf("The minimum of the rotated array {3, 4, 5, 1, 2} is %d.\n", findMinInRotatedArray(arr1, 0, 4));
printf("The minimum of the rotated array {1, 0, 1, 1, 1} is %d.\n", findMinInRotatedArray(arr2, 0, 4));
printf("The minimum of the rotated array {1, 1, 1, 0, 1} is %d.\n", findMinInRotatedArray(arr3, 0, 4));
printf("The minimum of the rotated array {1, 2, 3, 4, 5} is %d.\n", findMinInRotatedArray(arr4, 0, 4));
// Test index parameter exception
try {
findMinInRotatedArray(arr3, 5, 4);
}
catch(std::exception& e) {
std::cout << e.what() << std::endl;
};
}
int main(void)
{
unitest();
return 0;
}
Python 实现
#!/usr/bin/python
# -*- coding: utf8 -*-