二分查找的难点

二分查找有两种实现方式：
递归实现，循环迭代实现，相比而言，迭代循环实现比较有难度

递归实现方式

public static int binarySearch(int[] param, int target) {

        if (param.length == 0) {
            return -1;
        }
        int middleIndex = param.length / 2;
        int middleValue = param[middleIndex];
        if (target == middleValue) {
            return target;
        }
        while (target != middleValue && target < middleValue) {
            int[] leftParam = Arrays.copyOfRange(param, 0, middleIndex);
            int result = binarySearch(leftParam, target);
            if (result == target) {
                return result;
            }else {
                return -1;
            }
        }
        while (target != middleValue && target > middleValue) {
            int[] rightParam = Arrays.copyOfRange(param, middleIndex + 1, param.length);
            int result = binarySearch(rightParam, target);
            if (result == target) {
                return result;
            }else {
                return -1;
            }
        }
        return -1;
    }

迭代实现方式

public static int binarySearch(int[] param, int target) {

        if (param.length == 0) {
            return -1;
        }
        int left = 0;
        int right = param.length-1;
        while (left<=right){
            int middle = left +(right-left)/2;
            if(target == param[middle]){
                return middle;
            }else if(target<param[middle]){
                right = middle-1;
            }else if(target>param[middle]){
                left = middle+1;
            }
        }
        return -1;
    }

二者的不同在于，递归方式每次切割一半的数组作为入参，从而缩小查找范围
迭代方式改变索引搜索区间，每次左边索引移动，或者右边索引移动一个位置，缩小查询的区间范围

迭代法实现二分查找看似简单，但细节很难把握，容易陷进坑里。到底是“<=” 还是“<” ,到底是arrays.length 还是arrays.length-1? 很容易搞晕。正如发明 KMP 算法的Knuth大佬说的：Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...思维简单很简单，细节很磨人

下边就抽丝剥茧，给你捋清楚：
1 while (left<=right) 处到底应该是left<=right还是left<right呢？首先要明白，<= 就等价于[1,2,3] 闭合区间，而< 就等价于[1,2,3）就是左闭右开的区间。所以首先搞清楚最后一位是否包闭合

2 right的值应该是param.length-1，还是param.length，决定了是否闭合 如果right=param.length 那么就应该是开区间，否则会索引越界，反之，如果right=param.length-1 那么while中就是闭区间，包含等号。即满足这一条件的时候，还会进入while方法体，继续执行

3 为什么是left = mid+1; 因为while中的条件是闭合区间，所以本次搜索已经验证过mid位置处的值是否满足，所以右半边数组的起始索引就从下一位，即mid+1位置开始搜索。反之，如果搜索左半边数组，就从上一位，mid-1位置，搜索左半边位置，即right=mid-1;

4看完以后思路应该清晰了，但你会发现这个方法其实有很大的局限性，使用范围有限。比如说给你有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。

这样的需求很常见。常见的思路可能会想，找到一个 target 索引，然后向左或向右线性搜索不行吗？可以，但不是很好，脱离了二分查找的精髓了，因为这样难以保证二分查找对数级的复杂度了。

接下来通过一个案例所展示的技巧解决这个问题，让这个算法具有真正的实用价值。跟着我来一起学习吧。

下边是寻找左边界的代码

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;//原来这里会返回，但现在不返回，让循环继续
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

1为什么 while(left < right) 而不是 <= ?
解答：这个问题应该不难回答了吧，因为right = nums.length 也就是索引越界的位置，所以应该是<左闭右开的区间形式，不包含最后一位
2 while(left < right) 终止的条件是 left == right，此时搜索区间 [left, left) 恰巧为空，所以可以正确终止，不再进入循环体中
3为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办？这个需要一步步来，尤其要理解“左边界”的特殊含义：

left_bound.png

nums数组中小于target=2的元素有1个
比如对于有序数组 nums = [3,4,5,6], target = 2，算法会返回 0，含义是：nums 中小于 2 的元素有 0 个。如果 target = 9，算法会返回 4，含义是：nums 中小于 8 的元素有 4 个

结合以上分析可以看出：返回的值（即left左边界值）取值是闭区间[0,nums.length],所以我们简单添加两行代码就能在正确的时候 return -1：

nums[left] == target? left：-1

4 left =mid+1,right=mid 这还是符合我们之前说的，左边界右移，右边界左移
5 为什么该算法能够搜索左侧边界？
是下边这段代码

if (nums[mid] == target)
        right = mid;

这段代码的意思就是将右边界不断替换为最新的mid值，而mid值是不断减小的，在[left,mid) 位置上继续搜索，这一点确实不容易想到，也是技巧所在了