开始学算法（刷算法题）过程记录 10

题目描述：有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

本题考点：考察了对二分查找的理解。变换了二分查找的条件，对二分查找不熟悉的可以看这篇文章：二分查找法。

解题思路：

首先需要了解旋转数组的特点，旋转数组是将一个递增排序数组，最开始的若干个元素搬到数组的末尾。例如：[1,2,3,4,5,6]他的旋转数组可以是[4,5,6,1,2,3]、[2,3,4,5,6,1]、[6,1,2,3,4,5]等

我们拿[4,5,1,2,3]分析。

旋转数组的第一个元素应该大于等于最后一个元素。例如3>2

旋转数组可以看做2个递增的子数组，但是中间边界的位置是不确定的。我们可以通过比大小的办法来找出中间的边界。

具体我们可以拿数组中间的值 同 第一个元素和最后一个元素比较。第一个元素4是前一个递增序列的最小值。最后一个元素3是后一个递增序列的最大值。我们可以利用这个特点区分中间的数属于前序列还是后序列逐渐缩小范围找出2个递增序列的边界

例如在这个[4,5,1,2,3]中

中间数1 小于最后一个数字3。由此可见他是属于后面一个递增序列的。所以我们把high指针移动到1的位置上，重新选中间数。

中间数5 大于第一个数字4。由此可见他是属于前一个递增序列的。所以我们把low指针移动到5的位置上。

在这种high-low==1的情况下，就意味着边界找到了，此时high指针指的就是数组中最小的数。

但是当遇到low == high == mid的情况 这个办法就没有用了。如下图

无法通过比较端点值来判断中间数位于哪一个递增序列，只能顺序查找。

算法实现：

这题还可以用return Math.min(...Array)过。运行时间也差不多，实际项目中应该也是用这个。