題目描述
把一個數組最開始的的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉乐尊，輸出旋轉數組的最小元素盔性。例如仲锄，數組{3劲妙，4，5儒喊，1镣奋，2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1.
解題思路:
- 數組可以分為兩個遞增數組A和B怀愧，則第二個遞增數組B里的所有數字都小于等于第一個遞增數組A里的數字唆途。B的開頭即為最小數字。
- 采用二分查找的方式掸驱。用三個變量分別表示數組的開頭肛搬，中間和結尾。
- 如果中間數字大于等于開頭數字毕贼，則說明中間數字在遞增數組A里温赔，最小數字一定在中間數字之后。
- 再對中間數字之后的數字進行二分查找即可鬼癣。
代碼
int min(int[] arr){
if (arr == null || arr.length == 0) {
return -1;
}
int startIndex = 0;
int endIndex = arr.length - 1;
int middleIndex = startIndex;
// 如果開頭數字小于結尾數字陶贼，說明遞增數組并沒有旋轉，第一個數字就是最小數字待秃。
if (arr[startIndex] < arr[endIndex]) {
return arr[startIndex];
}
while(startIndex < endIndex) {
if (endIndex - startIndex == 1) {
return arr[endIndex];
}
middleIndex = startIndex + (endIndex - startIndex) / 2;
if (arr[startIndex] == arr[endIndex] && arr[startIndex] == arr[middleIndex]) {
// 三個值相等的話拜秧，采用順序查找的方式
int min = arr[startIndex];
for (int i = startIndex; i <= endIndex; i++) {
if (arr[i] < min) {
min = arr[i];
}
}
return min;
}
if (arr[middleIndex] >= arr[startIndex]) {
// middleIndex對應的數字在前面的遞增數組里，則最小值在middleIndex之后
startIndex = middleIndex;
} else if (arr[middleIndex] < arr[endIndex]) {
endIndex = middleIndex ;
}
}
return -1;
}
