题目描述
把一个数组最开始的的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组{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;
}
