binary-二分法

    @Test
    public void binary() {
        // 1. 输入一个有序的int类型数组
        int[] a = {
                1,  4,  6,  8,  21,
                34, 36, 41, 46, 49,
                50, 52, 57, 61, 62,
                64, 68, 69, 72, 75,
                77};
        System.out.println("a length: " + a.length);
        // 2. 再输入一个int整数
        int n = 75;
        // 3. 要求以最快的速度找到n在数组中的位置，不存在返回-1
        int location;
        if ((location = doBinary(a, n)) > 0)
            System.out.println("n在数组中的下标是:" + location);
        else
            System.out.println("n在数组中不存在:");
    }

    /**
     * 二分法
     */
    private int doBinary(int[] a, int n) {
        if (a == null || a.length == 0)
            return -1;
        int start = 0;
        int end = a.length;
        int middel;
        for (; ; ) {
            middel = (start + end) / 2; // 二分点
            if (n == a[middel])
                return middel;
            if (n < a[middel])
                end = middel;
            else
                start = middel;
            if (end - start == 1) // 判断n是否存在于数组中
                return -1;
        }
    }

二分法核心总结：
  数组可看成一个递增/递减区间，把数组从中间劈开分成左右两个子区间，如果N等于劈开位上的数则找到，否则以N所在子区间重复以上寻找过程，最终要么找到N，要么确定出数组中不存在N。

1. 区间各种位
   起始位 : start =0
   结束位 : end = length - 1
   中间位 : middle = (start + end) / 2
   劈位值 : T = a[middle]
2. N == T // 找到
3. N < T， N在左区间，所以新区间的 end = middle
4. N > T， N在右区间，所以新区间的 start = middle
5. end - start = 1 // 这种情况下，N不存在于数组中