剑指06.旋转数组的最小数字

{3 4 5 1 2} （一般情况）

{1 2 3 4 5} （特例，前面0个元素搬到后面，即已经排好序的情况）

{1 0 1 1 1} / {1 1 1 0 1}（特例，都可以看成递增排序数组{0 1 1 1 1 }的旋转）

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if (array.length == 0)
            return 0;
        int indexLeft = 0;
        int indexRight = array.length - 1;
        int indexMid = indexLeft; //如果旋转数组是排序数组本身，直接返回第一个数字
        while (array[indexLeft] >= array[indexRight]){
            if (indexRight - indexLeft == 1){
                indexMid = indexRight;
                break;
            }
            indexMid = indexLeft + (indexRight - indexLeft) / 2;
            //对于特例[1,0,1,1,1]和[1,1,1,0,1]
            //当两个指针指向的数字及它们中间的数字三者相同的时候；
            //无法判断中间的数字是位于前面的子数组还是后面的子数组，只能采用顺序查找的方法
            if (array[indexMid] == array[indexLeft] && array[indexMid] == array[indexRight]){
                return minInOrder(array, indexLeft, indexRight);
            }
            if (array[indexMid] >= array[indexLeft]){
                indexLeft = indexMid;
            }
            if (array[indexMid] <= array[indexRight]){
                indexRight = indexMid;
            }
        }
        return array[indexMid];
    }
    public int minInOrder(int[] array, int indexLeft, int indexRight){
        int result = array[indexLeft];
        for (int i = indexLeft + 1; i <= indexRight; i++){
            if (array[i] < result)
                result = array[i];
        }
        return result;
    }
}

int x = 1999999998;
int y = 1999999998;
int mid = (x+y) / 2;
int mid2 = x + (y-x) / 2;
System.out.println(mid); //-147483650
System.out.println(mid2); //1999999998