题目：把一个数组最开始的的若干元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
例如，数组{3，4，5，1，2}为数组{1，2，3，4，5}的一个旋转，该数组的最小值为1
分析
- 思路一
最直观的解法很容易想到，就是从头到尾遍历数组一次，然后就能找到最小元素，但是这种思路的时间复杂度显然为O(n)，而且也没有利用旋转数组的特点。
- 思路二
细想一下可以发现旋转之后的数组实际上可以划分为两个排序的子数组，而且前面排序的子数组的元素都大于或者等于后面子数组的元素，更重要的一点，最小的元素刚好是这两个子数组的分界线。
在排序的数组中可以使用二分查找法实现O(logn)的查找。和二分查找法一样，使用两个指针分别指向数组的第一个元素和最后一个元素。
接着可以找到数组中间的元素。如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中的最小元素应该位于该中间元素的后面，这时可以把第一个指针指向该中间元素缩小查找的范围，移动之后的第一个指针仍然位于前面的递增子数组。
同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组的最小元素应该位于该中间元素的前面，可以把第二个指针指向该中间元素，移动之后的第一个指针仍然位于后面的递增子数组。
不管移动第一个指针还是第二个指针，查找范围都会缩小到原来的一半。按照上述思路，第一个指针总是指向前面递增数组的元素，第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后应该元素，而第二个指针指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素。
可以借助下图理解过程
注意
虽然上面的分析包含了绝大多数的情况，但是仍然存在一种情况是我们并未考虑的，那就是第一个指针和第二个指针的值相等，并且中间位置的值也相等，这时候我们无法判断中间位置的值是属于第一个递增数组还是第二个递增数组，所以需要使用顺序查找来获取最小值。
C++算法实现
#include <iostream>
#include <exception>
using namespace std;
int MinInOrder(int *numbers, int index1, int index2);
int Min(int *numbers, int length)
{
if (numbers==nullptr || length < 0)
{
logic_error ex("Invalid parameters");
throw exception(ex);
}
int index1 = 0;
int index2 = length - 1;
int indexMiddle = index1;
while (numbers[index1] >= numbers[index2]) {
// 如果前后指针位置相差为1，那么index2就是我们要找的最小数
if (index2-index1 == 1)
{
indexMiddle = index2;
break;
}
// 计算中间位置
indexMiddle = (index1 + index2) / 2;
// 当index1，index2，indexMiddle3者相等，使用顺序查找获取最小值
if (numbers[index1] == numbers[index2] && numbers[indexMiddle] == numbers[index1])
{
return MinInOrder(numbers, index1, index2);
}
// 中间位置的值大于index1，将指针指向index1指向indexMiddle
if (numbers[indexMiddle] >= numbers[index1])
index1 = indexMiddle;
else if (numbers[indexMiddle] <= numbers[index2])
index2 = indexMiddle;
}
numbers[indexMiddle];
}
// 顺序遍历查找最小值
int MinInOrder(int *numbers, int index1, int index2)
{
int result = numbers[index1];
for (int i = index1 + 1; i <= index2; i++) {
if (result > numbers[i])
result = numbers[i];
}
return result;
}
测试功能
void Test(int* numbers, int length, int expected)
{
int result = 0;
try
{
result = Min(numbers, length);
for(int i = 0; i < length; ++i)
printf("%d ", numbers[i]);
if(result == expected)
printf("\tpassed\n");
else
printf("\tfailed\n");
}
catch (...)
{
if(numbers == nullptr)
printf("Test passed.\n");
else
printf("Test failed.\n");
}
}
int main(int argc, const char * argv[]) {
int array1[] = { 3, 4, 5, 1, 2 };
Test(array1, sizeof(array1) / sizeof(int), 1);
int array2[] = { 3, 4, 5, 1, 1, 2 };
Test(array2, sizeof(array2) / sizeof(int), 1);
int array3[] = { 3, 4, 5, 1, 2, 2 };
Test(array3, sizeof(array3) / sizeof(int), 1);
int array4[] = { 1, 0, 1, 1, 1 };
Test(array4, sizeof(array4) / sizeof(int), 0);
int array5[] = { 1, 2, 3, 4, 5 };
Test(array5, sizeof(array5) / sizeof(int), 1);
int array6[] = { 2 };
Test(array6, sizeof(array6) / sizeof(int), 2);
Test(nullptr, 0, 0);
return 0;
}
