1.題目描述
把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾山卦，我們稱之為數(shù)組的旋轉(zhuǎn)腹泌。
輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)褐澎，輸出旋轉(zhuǎn)數(shù)組的最小元素岩臣。
例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)脚牍，該數(shù)組的最小值為1向臀。
NOTE：給出的所有元素都大于0，若數(shù)組大小為0诸狭，請返回0券膀。
2.解題思路
采用二分法解答這個問題，
mid = low + (high - low)/2
需要考慮三種情況：
(1)array[mid] > array[high]:
出現(xiàn)這種情況的array類似[3,4,5,6,0,1,2]驯遇，此時最小數(shù)字一定在mid的右邊芹彬。
low = mid + 1
(2)array[mid] == array[high]:
出現(xiàn)這種情況的array類似 [1,0,1,1,1] 或者[1,1,1,0,1]，此時最小數(shù)字不好判斷在mid左邊
還是右邊,這時只好一個一個試 叉庐，
high = high - 1
(3)array[mid] < array[high]:
出現(xiàn)這種情況的array類似[2,2,3,4,5,6,6],此時最小數(shù)字一定就是array[mid]或者在mid的左
邊舒帮。因為右邊必然都是遞增的。
high = mid
注意這里有個坑：如果待查詢的范圍最后只剩兩個數(shù)陡叠，那么mid 一定會指向下標靠前的數(shù)字
比如 array = [4,6]
array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果high = mid - 1会前，就會產(chǎn)生錯誤， 因此high = mid
但情形(1)中l(wèi)ow = mid + 1就不會錯誤
package com.wuli.algorithm.旋轉(zhuǎn)數(shù)組;
/**
* @author wuli
* @date 2019/12/17
*
* 把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾匾竿，我們稱之為數(shù)組的旋轉(zhuǎn)瓦宜。
* 輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素岭妖。
* 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)临庇，該數(shù)組的最小值為1。
* NOTE：給出的所有元素都大于0昵慌，若數(shù)組大小為0假夺，請返回0。
*/
public class Solution {
public int minNumberInRotateArray(int[] array) {
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];
}
}
