題目描述
把一個(gè)數(shù)組最開始的若干個(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。 NOTE：給出的所有元素都大于 0坑傅，若數(shù)組大小為 0僵驰，請(qǐng)返回 0。
思路分析
其實(shí)題目的本身要求，就是「查找」出數(shù)組最小的數(shù)字蒜茴，按照順序查找星爪，也是可以的，時(shí)間復(fù)雜度為 O(n) 粉私，但沒(méi)有好好利用「旋轉(zhuǎn)數(shù)組」的特性顽腾。
觀察可知，旋轉(zhuǎn)之后的數(shù)組實(shí)際上可以劃分成兩個(gè)有序的子數(shù)組：前面子數(shù)組的數(shù)字都大于后面子數(shù)組中的數(shù)字诺核。
而且實(shí)際上最小的元素就是兩個(gè)子數(shù)組的分界線抄肖。本題目給出的數(shù)組一定程度上是排序的，因此我們?cè)囍枚植檎曳▽ふ疫@個(gè)最小的元素窖杀。
mid = low + (high - low)/2
需要考慮三種情況：
(1)array[mid] > array[high]:
出現(xiàn)這種情況的array類似[3,4,5,6,0,1,2]漓摩，此時(shí)最小數(shù)字一定在mid的右邊。
low = mid + 1
(2)array[mid] == array[high]:
出現(xiàn)這種情況的array類似 [1,0,1,1,1] 或者[1,1,1,0,1]陈瘦，此時(shí)最小數(shù)字不好判斷在 mid 左邊幌甘，還是右邊,這時(shí)只好一個(gè)一個(gè)試 ，
high = high - 1
(3)array[mid] < array[high]:
出現(xiàn)這種情況的array類似[2,2,3,4,5,6,6],此時(shí)最小數(shù)字一定就是array[mid]或者在mid的左邊痊项。因?yàn)橛疫叡厝欢际沁f增的锅风。
high = mid
注意這里有個(gè)坑：如果待查詢的范圍最后只剩兩個(gè)數(shù)，那么mid 一定會(huì)指向下標(biāo)靠前的數(shù)字
public static class Solution {
public int minNumberInRotateArray(int [] array) {
if (array.length == 0){
return 0;
}
int low = 0 ; int high = array.length - 1;
while(low < high){
int mid = low + (high - low) / 2;
if(array[mid] > array[high]){
low = mid + 1;
}else if(array[mid] == array[high]){
high = high - 1;
}else{
high = mid;
}
}
return array[low];
}
}
比如 array = [4,6]
array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果high = mid - 1鞍泉，就會(huì)產(chǎn)生錯(cuò)誤皱埠， 因此high = mid
但情形(1)中l(wèi)ow = mid + 1就不會(huì)錯(cuò)誤
這道題我不是那么理解，所以引用趴裕客網(wǎng)的大佬解題思路边器。
參考文獻(xiàn)
https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba
https://blog.csdn.net/my_learning_road/article/details/79524362
