把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。

給你一個(gè)可能存在 重復(fù) 元素值的數(shù)組 numbers ，它原來是一個(gè)升序排列的數(shù)組，并按上述情形進(jìn)行了一次旋轉(zhuǎn)。請返回旋轉(zhuǎn)數(shù)組的最小元素。例如，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一次旋轉(zhuǎn)，該數(shù)組的最小值為 1。

注意，數(shù)組 [a[0], a[1], a[2], ..., a[n-1]] 旋轉(zhuǎn)一次 的結(jié)果為數(shù)組 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

示例1

• 輸入：numbers = [3,4,5,1,2]

• 輸出：1

示例2

• 輸入：numbers = [2,2,2,0,1]

• 輸出：0

提示

• n == numbers.length

• 1 <= n <= 5000

• -5000 <= numbers[i] <= 5000

• numbers 原來是一個(gè)升序排序的數(shù)組，并進(jìn)行了 1 至 n 次旋轉(zhuǎn)

算法：二分法

首先，從審題中我們了解到，

• 條件一：“原來是一個(gè)升序排列的數(shù)組”，說明他是一個(gè)有順序的數(shù)組，即左邊的數(shù)小于等于右邊的數(shù)。

• 條件二：“把最開始的若干個(gè)元素搬到數(shù)組末尾”，說明最小數(shù)字是在數(shù)組中，可以把旋轉(zhuǎn)后的數(shù)組理解為“兩個(gè)有序的數(shù)組”。

因?yàn)閿?shù)組是“可能存在重復(fù)”的，所以有兩種情況“不重復(fù)數(shù)組”和“重復(fù)數(shù)組”。

場景一：不重復(fù)數(shù)組

原數(shù)組：[1,2,3,4,5]，經(jīng)過一次旋轉(zhuǎn)變?yōu)椋篬3,4,5,1,2]。

首先我們?nèi)≈虚g值 “5” 跟最右側(cè)的 “2” 比較，發(fā)現(xiàn) 5 > 2 ，說明數(shù)組中的最小值在中間值 “5” 的右側(cè)，然后我們右側(cè)值取 “1” 跟中間值側(cè)的 “5” 比較，發(fā)現(xiàn) 1 < 5，即該值為最小值。

場景二：重復(fù)數(shù)組

原數(shù)組：[0,1,2,2,2]，經(jīng)過一次旋轉(zhuǎn)變?yōu)椋篬2,2,2,0,1]。

首先我們?nèi)≈虚g值 “2” 跟最右側(cè)的 “1” 比較，發(fā)現(xiàn) 2 > 1，說明數(shù)組中的最小值在中間值 “2” 的右側(cè)，然后我們右側(cè)值取 “0” 跟中間值側(cè)的 “2” 比較，發(fā)現(xiàn) 0 < 2，即該值為最小值。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度 ：log以2為底n的對(duì)數(shù)， 在特例情況下（例如 [1, 1, 1, 1]），會(huì)退化到 O(N)。

• 空間復(fù)雜度 ：O(1)， low , high , pivot 變量使用常數(shù)大小的額外空間。

END

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。