旋转数组的最小数字

问题：

把一个数组最开始的若干元素搬到数组末尾

输入一个递增排序数组的一个旋转，输出该元素的最小值

如｛3，4，5，1，2｝为｛1，2，3，4，5｝的一个旋转数组

输出最小值为1

思路：

递增数组的旋转，二分法思维，中间值分成两个区域，一定一边有序，一边无序。

中间值比最左值大 左侧有序 否则 右侧有序

且最小的数一定在无序的一侧（因为最小的数一定是原数组中第一个数）每次切掉

有序的一半，直到剩下两个元素，最小的数一定是第二个数。

如果原数组是特殊的形如全部相等元素的数组，则考虑遍历法找到最小的数。

(Java代码参考)

public static void main(String[] args) {

int[] a = {3,4,5,1,2};

// int[] a = {1,1,1,0,1};

int res = min(a);

System.out.println(res);

}

static int min(int[] arr) {

int begin = 0;

int end = arr.length-1;

//没有旋转

if(arr[begin] < arr[end]) return arr[begin];

//直到只剩两个元素结束

while(begin + 1 < end) {

int mid = begin + ((end - begin)>>1);

if(arr[begin] == arr[mid] || arr[end] == arr[mid]) {//特殊数组

int minIndex = 0;

int min = arr[0];

for(int i = 0; i < arr.length; i++) {

if(arr[i] < min) {

minIndex = i;

min = arr[i];

}

}

return arr[minIndex];

}

if(arr[mid] > arr[begin]) {//左边有序

begin = mid;

}else {//右边有序

end = mid;

}

}

return arr[end];//最后剩两个数，右边的一定是最小的

}