BinarySearch

举个非常简单的例子 在[0,1,2,3,4,5,6,7,8,9,10] 这个数列中找到7所在的位置，最简单的做法就是遍历数组，即复杂度为O(n)。继续观察以上数列的特点 有序 ，于是可以上二分查找，优化复杂度为O(log(n))。
再一个现实点的例子，1-100 在纸上随机写一个数，最少多少次能猜到就是用的二分查找的原理。

实际上手写二分并不是一件容易的事情，可能会出现死循环，查找不对的情况，需要根据要求对边界进行调整。接下来就由简到繁尝试下不同情况的二分写法。

（一）数据有序且唯一、目标值存在

如开题中描述的数据[0,1,2,3,4,5,6,7,8,9,10]，目标值为7的情况。首先设定查找边界

    int l = 0;
    int r = 10;

根据折中的原则，定义第一次猜的位置

    int mid = (l + r) >> 1;   // l = 0 ,r = 10 mid = 5

5小于目标值7，即目标在mid的右边，将左边界进行调整

    l = mid + 1;    // 5 + 1 = 6

再一次进行尝试 mid = (6 + 10) >> 1; //mid = 8

8大于目标值7，即目标在mid的左边，将右边界进行调整

    r = mid - 1;    // 8 - 1 = 7

again, mid = (6 + 7) >> 1; //mid = 6

调整 l = 7； mid = 7； 最终得到结果，共计4次。

完整代码：

public int fun1(int[] array, int target) {

    int l = 0;
    int r = array.length - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (array[mid] < target) {
            l = mid + 1;
        } else if (array[mid] > target) {
            r = mid - 1;
        } else {
            return mid;
        }
    }
    return l;
}

测试数据：
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] target = 7
l = 0 r = 10 mid = 5
l = 6 r = 10 mid = 8
l = 6 r = 7 mid = 6
l = 7 r = 7 mid = 7
结果：7

（二）数据有序且唯一、目标值不一定存在

在Java源码中 Arrays 和 Collections 两个类提供了二分的工具类，采用返回-值的方式表示目标值未找到

    return -(low + 1);  // key not found.

可以思考下这里为什么要+1？

另外还可以通过 ~low的方式 有同样的效果。

完整代码：

public int fun1(int[] array, int target) {

    int l = 0;
    int r = array.length - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (array[mid] < target) {
            l = mid + 1;
        } else if (array[mid] > target) {
            r = mid - 1;
        } else {
            return mid;
        }
    }
    return ~l;
}
测试数据：
array = [0, 1, 2, 3, 4, 6, 7, 8, 9, 10] target = 5
l = 0 r = 9 mid = 4
l = 5 r = 9 mid = 7
l = 5 r = 6 mid = 5
结果：-6

（三）数据有序且唯一、目标值不一定存在，目标不存在时返回小于目标值的最大值（大于目标值的最小值思路相同，以下不举例）

在（一）时，如果mid不是目标时会跳过mid直接取 l = mid + 1 或者 r = mid - 1 的，
但是本题条件不同，在mid不匹配目标值时，也是有可能作为查找的结果。
如 数据[0,1,3,4]，目标值为2的情况。通过（一）的代码得到结果为2，实际想要的结果为1。

测试数据：
array = [0, 1, 3, 4] target = 2
l = 0 r = 3 mid = 1
l = 2 r = 3 mid = 2
结果：2

很直接的想到可以改变边界，可放宽左边界范围，即查询的值小于目标值时 l = mid。
修改代码后进行尝试。

public int fun(int[] array, int target) {
    int l = 0;
    int r = array.length - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (array[mid] < target) {
            l = mid;
        } else if (array[mid] > target) {
            r = mid - 1;
        } else {
            return mid;
        }
    }
    return l;
}

测试数据：
array = [0, 1, 3, 4] target = 2
l = 0 r = 3 mid = 1
l = 1 r = 3 mid = 2
l = 1 r = 1 mid = 1
l = 1 r = 1 mid = 1
。。。。。。。。。。。。。。。。

发现运行半天出不了结果，GG死循环。通过调试发现l=r=1时，mid=1，但与能够找到目标值不同，这并不是答案，一直进入 array[mid] < target 。接着又对代码进行修改，去掉循环中的等于号进行尝试，完美找到了想要的答案。

public int fun(int[] array, int target) {
    int l = 0;
    int r = array.length - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (array[mid] < target) {
            l = mid;
        } else if (array[mid] > target) {
            r = mid - 1;
        } else {
            return mid;
        }
    }
    return l;
}

测试数据：
array = [0, 1, 3, 4] target = 2
l = 0 r = 3 mid = 1
l = 1 r = 3 mid = 2
结果：1

但是，将数据换成[0,1,3]，目标值仍是2，运行。。。依旧是死循环。

测试数据：
array = [0, 1, 3] target = 2
l = 0 r = 2 mid = 1
l = 1 r = 2 mid = 1
l = 1 r = 2 mid = 1
。。。。。。。。。。。。。。。。。

当l = 1，r = 2时，mid = （ 1 + 2 ）/ 2 = 1 ，在这个条件下造成了死循环（虽然得到了结果1，但是边界无法收敛）。于是通过修改 mid = (l + r + 1) >> 1 修正逻辑

public int fun(int[] array, int target) {
    int l = 0;
    int r = array.length - 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (array[mid] < target) {
            l = mid;
        } else if (array[mid] > target) {
            r = mid - 1;
        } else {
            return mid;
        }
    }
    return l;
}

测试数据：
array = [0, 1, 3] target = 2
l = 0 r = 2 mid = 1
l = 1 r = 2 mid = 2
结果：1

假如将目标值设为-1，即小于目标值的最大值不存在的情况，这就根据题意进行处理。

此题完毕，另一种情况目标不存在时返回大于目标值的最小值自己理解后对上面代码进行对应调整即可。

（四）已知目标值在一个有序列表中重复出现，求第一次出现的位置（最后一次出现的位置、重复出现的次数）

在以上几个题目中，当array[mid]值等于目标值时，就是最终的结果直接返回。这里因为目标值有多个，将等于的逻辑合并到array[mid] > target中，逻辑上等同于找到小于目标值的最大值的位置。

public int fun(int[] array, int target) {
    int l = 0;
    int r = array.length - 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (array[mid] < target) {
            l = mid;
        } else if (array[mid] >= target) {
            r = mid - 1;
        }
    }
    return l;
}

测试数据：
array = [0, 1, 3, 3, 3, 3, 3, 3, 4] target = 3
l = 0 r = 8 mid = 4
l = 0 r = 3 mid = 2
l = 0 r = 1 mid = 1
结果：1

这里的结果并不是最终结果，需要对array[l]和array[l+1]进行判断。

若重复的数值唯一（即除了目标值其他均不重复），这种特殊情况可作为（三）的延伸。寻找等于（target-1）或小于（target-1）的最大值或等于（target+1）或小于（target+1）的最小值。

继续扩展求目标值的个数，即求第一次出现和最后一次的位置的差值，不再做分析。

总结

上诉只是讲了几种常见的二分的写法，二分的前提是有序的数组，然后需要重点思考

1. 目标值存不存在
2. 不存在时，是取前者还是后者（边界如何收缩）
3. 重复时怎么取值
4. 边界情况取值
   。。。

二分的思想很简单，代码量也很少，但是在文章开头也提到过，手写二分真不是一件容易的事情。