转载本文，请联系牛逼程序员K公众号。前言将数组的前几个元素移动到数组的末尾称为数组的旋转。有一个升序排列的数组，将开头的几个元素移动到数组的末尾，找到其中的最小值。本文将与大家分享如何以最快的速度找到增量旋转数组中的最小值。欢迎有兴趣的开发者阅读本文。实现思路乍一看这个问题，一些开发者首先想到的解决办法就是从头到尾遍历数组，这样就可以找到最小的元素。这个思路的时间复杂度是O(n)，没有用到题中的条件，所以这个解不是本题的正确答案。实例分析下面我们来分析一下题目，通过实例和观察来寻找突破口。让我们从枚举一个递增数组开始。如上图所示，我们准备了一个从1到5递增的数组，然后将前两个元素移到数组的末尾，这样就形成了一个旋转数组。经过一番观察，我们可以发现：旋转后的数组可以分成两个排序好的小数组前面的子数组的元素都大于等于后面的子数组的元素最小的数就是分界线两个子数组之间的二分查找经过上面的分析，我们知道旋转后的数组在一定程度上是有序的，那么我们可以尝试使用二分查找的思想来寻找最小的元素。接下来我们准备两个指针（左指针，右指针），左指针指向数组首元素，右指针指向数组尾元素，如下图所示：如图，我们发现他们中间的元素是5，最小值在5后面，所以我们可以排除中间值之前的元素，将左指针移动到5，如下图：此时，他们的中间的元素是1，我们发现最小值的前面是2，所以我们可以把右边的指针移到中间的1，如下图：在图片的最后，我们发现左边的指针紧挨着右指针，右指针指向的元素恰好是旋转数组的最小元素。经过上面的绘图分析，我们可以得到如下规则：如果两个指针的中间元素大于等于左指针指向的元素，那么最小值一定在中间元素后面，移动左指针到中间值位置以缩小搜索范围。如果两个指针的中间元素小于等于右指针所指向的元素，那么最小值一定在中间元素的前面。将右指针移动到中间值以缩小搜索范围。数组当左右指针相邻时，右指针指向的元素为数组的最小值时间复杂度分析：每移动一次指针，查找范围就会缩小到原来的一半，所以总时间复杂度为O(logn)特例以上规则可以满足大部分情况，当出现如下情况时，我们不能使用二分查找：当数组的第0个元素小于最后一个元素时，证明数组已排序，其最小值是数组的第0个元素。当左指针和右指针指向的元素相同且中间元素也相同时，则只能使用顺序查找，如下图：实现代码接下来我们将在上面的基础上内容总结思路：判断数组是否排序（第一个元素是否小于最后一个元素）如果左指针指向的值大于等于右指针指向的值，则左移和right指针根据条件：循环终止条件：left指针与right指针相邻找到左右指针的中间索引。左指针指向的值与右指针指向的值相同，中间元素也相同（使用顺序查找）如果中间值大于或等于所指向的值左指针，将左指针位置的中间值移动到中间值位置，小于等于右指针指向的值，将右指针位置移动到中间值位置，循环结束，返回最小值。代码如下：//将数组的前几个元素移动到数组的最后，我们调用数组的旋转。//输入一个升序排列的数组的旋转，输出旋转后数组的最小元素。//比如数组[3,4,5,1,2]是[1,2,3,4,5]的旋转，数组的最小值为1。exportdefaultclassFindWhirlingArrayMinVal{privateleftPointer;privaterightPointer;privatemiddleIndex;constructor(){this.leftPointer=0;this.rightPointer=0;this.middleIndex=0;}publicgetMinValue(incrementArray:Array
