二分查找详解

首先有几个数字要注意
下位中位数

median = (length - 1) / 2

指针的区间全部选择闭区间,即[low, high]，所以low的初始值为0，high的初始值为array.length - 1。注意

median = ( low + high ) / 2 // OVERFLOW

接下来很重要的一点是终止条件，这里一律设为low > high时终止，即while内部为(low <= high)，搜索区间为空的时候，low一定会在high的右边一格。
返回值不需要纠结，返回值大胆返回low或者low的变体（+1或者-1之类的），因为查找的过程实际上是维护low指针的过程：low从0开始，以查找某个数为例，只有确保在mid指向的那个数小于target时，low才会+1，而high指针则是要把所有不满足条件或者满足一部分的数字全部排除，最后low指针就会指向第一个有可能是正确答案的数（low前面都是被排除掉的数），这时候high将会小于low，循环终止，如果array[low] == target，则找到，否则就是没找到。
无重复有序数组中查找数字（非递归版）：

递归版

如果有重复数字，则要查找的是那个数字出现的最左边索引和最右边索引，其中最左边索引其实就是寻找大于等于target的第一个数字，最右边索引就是寻找大于target的第一个数字的左边一个的索引。
leetcode34题