題目描述：有一個(gè)長度為 n 的非降序數(shù)組，比如[1,2,3,4,5]，將它進(jìn)行旋轉(zhuǎn)，即把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，變成一個(gè)旋轉(zhuǎn)數(shù)組，比如變成了[3,4,5,1,2]，或者[4,5,1,2,3]這樣的。請問，給定這樣一個(gè)旋轉(zhuǎn)數(shù)組，求數(shù)組中的最小值。

本題考點(diǎn)：考察了對二分查找的理解。變換了二分查找的條件，對二分查找不熟悉的可以看這篇文章：二分查找法。

解題思路：

首先需要了解旋轉(zhuǎn)數(shù)組的特點(diǎn)，旋轉(zhuǎn)數(shù)組是將一個(gè)遞增排序數(shù)組，最開始的若干個(gè)元素搬到數(shù)組的末尾。例如：[1,2,3,4,5,6]他的旋轉(zhuǎn)數(shù)組可以是[4,5,6,1,2,3]、[2,3,4,5,6,1]、[6,1,2,3,4,5]等

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

旋轉(zhuǎn)數(shù)組的第一個(gè)元素應(yīng)該大于等于最后一個(gè)元素。例如3>2

旋轉(zhuǎn)數(shù)組可以看做2個(gè)遞增的子數(shù)組，但是中間邊界的位置是不確定的。我們可以通過比大小的辦法來找出中間的邊界。

具體我們可以拿數(shù)組中間的值 同 第一個(gè)元素和最后一個(gè)元素比較。第一個(gè)元素4是前一個(gè)遞增序列的最小值。最后一個(gè)元素3是后一個(gè)遞增序列的最大值。我們可以利用這個(gè)特點(diǎn)區(qū)分中間的數(shù)屬于前序列還是后序列逐漸縮小范圍找出2個(gè)遞增序列的邊界

例如在這個(gè)[4,5,1,2,3]中

中間數(shù)1 小于最后一個(gè)數(shù)字3。由此可見他是屬于后面一個(gè)遞增序列的。所以我們把high指針移動(dòng)到1的位置上，重新選中間數(shù)。

中間數(shù)5 大于第一個(gè)數(shù)字4。由此可見他是屬于前一個(gè)遞增序列的。所以我們把low指針移動(dòng)到5的位置上。

在這種high-low==1的情況下，就意味著邊界找到了，此時(shí)high指針指的就是數(shù)組中最小的數(shù)。

但是當(dāng)遇到low == high == mid的情況 這個(gè)辦法就沒有用了。如下圖

無法通過比較端點(diǎn)值來判斷中間數(shù)位于哪一個(gè)遞增序列，只能順序查找。

算法實(shí)現(xiàn)：

這題還可以用return Math.min(...Array)過。運(yùn)行時(shí)間也差不多，實(shí)際項(xiàng)目中應(yīng)該也是用這個(gè)。