面试题：找出旋转数组中的最小元素

summary

:

在《剑指Offer》里面看到的一道题，非常有趣。

题目

把数组的开头一部分元素放到数组的末尾得到的新数组称为原数组的旋转。现在输入一个 递增排序的数组的旋转，如{3, 4, 5, 1, 2}，找到这个数组的最小值（这里是1）。

分析

不可能直接遍历一次找到最小值。

本人比较笨，想不出来办法，看了书上的解析才知道，可以用二分查找的思想。当时觉得 太神了。方法是这样的：用left记录整个数组的第一个元素的下标，right记录最后一个 元素的下标，求两个下标的中间下标mid，如果mid指向的元素比left指向的要大，则说明 mid所在的范围为原数组递增的部分，这个时候把left改为mid，缩小了范围。如果mid 指向的元素比left指向的要小，说明mid所在的范围为旋转的那部分，这个时候把right 改成mid，缩小了范围。继续下去，直到left和right相邻。

比如：

{5, 6, 6, 7, 8, 1, 1, 1, 2, 3}

left指向的元素为5, right指向的为3, mid指向的为8, 8比5大，则8所在的范围为原数组 递增的部分，这时left修改为指向8。再求mid，指向的为第二个1, 比8小，说明1在旋转 部分，则把right改成指向它。这时范围变成了8, 1, 1。再计算，mid指向的为第1个1,再 把right指向第1个1,范围变成了8,1。这时，已经可以计算出来最小值是1了。

特殊情况：

• 没有旋转。这个时候，right指向的元素一定比left指向的要大，我直接就返回left指向 的了。
• 当left, mid和right指向的元素都相等的情况下，居然是无法用二分查找的思想解决的。 比如，对于{1, 0, 1, 1, 1}来说，left, mid, right指向的元素都相等，那么mid是在 哪个范围呢？这个例子是在旋转部分。而对于{1, 1, 1, 0, 1}来说，left, mid, right 指向的元素也相等，但是mid是在原数组递增部分。而两个数组都是{0, 1, 1, 1, 1}的 旋转。这就无法确定了。于是就直接线性查找了。但是也不是线性扫一遍求最小值。而是 有技巧的。由于没有旋转这个特殊情况已经在一开始判断了，后面的肯定是旋转过的，则 中间遇到的第一个比第一个元素小的元素肯定是最小的元素了。

我的代码

::: {.code-include lexer="cpp"} ./rotated-array-smallest-element.cpp :::

使用了Boost的单元测试框架，链接的时候要加上 -lboost_unit_test_framework 参数。