把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾否彩，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)托享，輸出旋轉(zhuǎn)數(shù)組的最小元素其兴。例如顶瞒，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1元旬。
最簡(jiǎn)單的方法就是遍歷榴徐，直接遍歷一次數(shù)組找到其中的最小值，時(shí)間復(fù)雜度O(n)法绵。
算法一：
func minArray(_ numbers: [Int]) -> Int {
guard numbers.count > 0 else {
return -1
}
var min = numbers[0]
for num in 1..<numbers.count {
if min > numbers[num] {
min = numbers[num]
}
}
return min
}
算法一是一種暴力的解法箕速，我們可以根據(jù)旋轉(zhuǎn)數(shù)組的特性來(lái)優(yōu)化酪碘，旋轉(zhuǎn)后的數(shù)組實(shí)際上可以劃分為兩個(gè)排序好的子數(shù)組朋譬。而且前面的子數(shù)組元素都大于后面子數(shù)組的元素。而最小元素是這兩個(gè)子數(shù)組的分界線兴垦。在排序的數(shù)組查找元素我們可以通過(guò)二分查找提供性能徙赢。該題給出的數(shù)組一定程度上也是排序的字柠，所以也可以通過(guò)二分查找來(lái)尋找最小元素。
在二分查找的每一步中狡赐，左邊界為low窑业，右邊界為high，區(qū)間的中點(diǎn)為 indexMid枕屉，最小值就在該區(qū)間內(nèi)常柄。我們將中軸元素 numbers[indexMid]與右邊界元素 numbers[high] 進(jìn)行比較，可能會(huì)有以下的三種情況：
第一種情況是 numbers[indexMid]<numbers[high]搀擂。這說(shuō)明numbers[indexMid]是最小值右側(cè)的元素西潘，因此我們可以忽略二分查找區(qū)間的右半部分。
第二種情況是 numbers[indexMid]>numbers[high]哨颂。這說(shuō)明 numbers[indexMid]是最小值左側(cè)的元素喷市，因此我們可以忽略二分查找區(qū)間的左半部分。
第三種情況是 numbers[indexMid]==numbers[high]威恼。如下圖所示品姓，由于重復(fù)元素的存在，我們并不能確定numbers[indexMid]究竟在最小值的左側(cè)還是右側(cè)箫措，因此我們不能莽撞地忽略某一部分的元素腹备。我們唯一可以知道的是，由于它們的值相同蒂破，所以無(wú)論numbers[high]是不是最小值馏谨，都有一個(gè)它的「替代品」numbers[indexMid]，因此我們可以忽略二分查找區(qū)間的右端點(diǎn)附迷。
算法二：
func minArray(_ numbers: [Int]) -> Int {
var low = 0
var high = numbers.count - 1
while low < high {
let indexMid = low + (high - low)/2
if numbers[indexMid] < numbers[high] {
high = indexMid
}else if numbers[indexMid] > numbers[high] {
low = indexMid + 1
}else {
high -= 1
}
}
return numbers[low]
}
時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度為 O(\log n)O(logn)
