面试题11: 旋转数组的最小数字

package cn.zxy.interview;

/**
 * 分析:
 * 二分法 数组的最小元素将旋转数组分为两个递增子数组 选择中间元素, 判断其在前面的子数组还是后面的子数组
 * 如何判断?
 * 如果中间元素大于等于前面的元素, 则认为该中间元素属于前子数组, 如[4, 5, <5>, 1, 1, 2]
 * 如果中间元素小于等于后面的元素, 则认为该中间元素属于后子数组, 如[4, 5, <1>, 1, 2, 3]
 *
 * 如果属于前面, 将前指针置为mid; 如果属于后面, 将后指针置为mid, 最小元素总是在前后指针之内;
 * 直到前后指针相差距离为1, 后指针指向后半子数组最小元素, 也就是要找的最小元素
 *
 */
public class A11_MinInRotateArray {
    public static int minNumber(int[] a){
        if(a == null || a.length == 0) return -1;
        if(a.length == 1) return a[0];

        int p1 = 0;
        int p2 = a.length-1;
        int mid = p1;

        while(a[p1] >= a[p2]){
            if (p2 - p1 == 1){
                mid = p2;
                break;
            }

            mid = p1 + (p2-p1) / 2;
            if(a[mid] >= a[mid-1]){
                p1 = mid;
            }else if(a[mid] <= a[mid+1]){
                p2 = mid;
            }
        }

        return a[mid];
    }


    public static void main(String[] args) {
        int[] a = {1};
        int num = minNumber(a);
        System.out.println(num);
    }
}