聊聊算法——二分查找算法深度分析

vlambda
2020-07-07

聊聊算法——二分查找算法深度分析

今天我想说下二分查找算法，可能各位看官都觉得二分查找很简单，没啥可说的，但魔鬼在细节，二分查找的各临界值处理，二分查找的局限性，二分查找的变形算法，甚至是衍生出来的三分查找、四分查找，都值得思考一番，如此经过一番折腾，或许才算真正掌握了二分查找算法的精髓了！

准备：

Idea2019.03/JDK11.0.4

难度：新手--战士--老兵--大师

目标：

深度理解二分查找算法

1 算法框架

先看二分算法框架：

private static int binary_search(List<Integer> list,int target){
    int left = 0;
    int right = list.size()-1;
    while (...){
        int mid = left + (right - left)/2;
        if (list.get(mid) == target){
            right = ...;
        }
        else if (list.get(mid) > target){
            right = ...;
        }else if (list.get(mid) < target){
            left = ...;
        }
    }
    return ...;
}

思路很简单：对有序列表先比较中间位置的数，如果相等，即找到目标；如果中间值比目标值大，则在小端的一半范围内查找；如果中间值比目标值小，则在大端的另一半范围去查找，如此迭代下去。

这里我提出几个问题：

1.left + (right - left)/2 为啥不直接写成 (left + right)/2?

2.中间值mid为非整数时有无问题?

3.right是否可以写为right = list.size()？

答：1 (left + right)很大时可能会int越界，而left + (right - left)/2 则安全；

2 mid为非整数时，由于int类型限制，会自动转换处理，只会导致分割出来的两个范围长度不等，但不影响最终结果；

3可以写为right = list.size()，但while循环中的终止条件则需要对应调整，见后文分析；

2 小试牛刀

有了框架，再来解决问题，先来个常规的二分查找：输出目标值在列表中的序号值，没有则输出 -1 ，java完整版：

public class BinarySearch {
    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(6, 7, 8, 1, 2, 3, 4, 5);
        Collections.sort(nums);
        System.out.println(nums);
        int res = findIndex(nums,1);
        System.out.println(res);
    }

    private static int findIndex(List<Integer> list,int target){
        int left = 0;
        int right = list.size() -1;
        while (left <= right){
            int mid = left + (right - left)/2;
            System.out.println("mid >> "+ mid);
            if (list.get(mid) == target){
                return mid;
            }else if (list.get(mid) < target){
                left = mid +1;
            }else if (list.get(mid) > target){
                right = mid -1;
            }
        }
        return -1;
    }

请看官思考问题：

1.如果上面写为right = list.size()，会发生什么？答：若如此，则可知list.get(list.size()) 是越界的。而while (left <= right) 的循环终止条件为left > right，即达到 left = right + 1时，设想target比所有值大时，最终会mid= list.size()，发生越界异常。

2.如果我非要写为right = list.size()，可以吗？答：若修改代码为while (left < right) ，则循环终止条件为left = right，即使target比所有值都大时，也只会达到left = right= list.size()，而此时已经终止循环，不会发生越界，故理论上可行。

3.如果写为right = list.size()，有无算法漏洞？答：由上可知，while (left < right)循环终止条件为left = right，对于以上示例代码，当查找target为1时，循环终止条件为left = right=0，而此时循环已经终止，最终导致漏掉了list.get(0)的元素，输出为-1，因此我们需补上漏洞：

//return -1;
return list.get(left) == target? left : -1;

3 进阶思考

如果我们遇到数组 {1, 2, 3, 3, 3, 4, 5, 6, 7, 8} ，还是运用上面二分查找算法，会是什么结果？若采用right = list.size()-1写法，则答案是4，因为第一次mid直接匹配成功即结束；若采用right = list.size()写法，则答案是2，因为第二次mid匹配成功即结束，由此可见常规二分查找还是有其局限性的，需要求元素唯一；那么现在题目要求变为，找出最左侧匹配目标的序号值，即左侧边界，如何来利用二分查找框架来改写实现？

分析：需要寻找左侧边界，那么我们在每次二分的时候，就应该缩小右侧边界，直到循环终止。先给出一个可行代码方案A：

private static int left_bound(List<Integer> list,int target){
    int left = 0;
    int right = list.size();
    while (left < right){
        int mid = left + (right - left)/2;
        if (list.get(mid) == target){
           right = mid;
        }
        else if (list.get(mid) > target){
            right = mid;
        }else if (list.get(mid) < target){
            left = mid + 1;
        }
    }
    return left;
}

以上代码分析：

1.寻找左边界，每次二分，若中间值等于目标，左边界肯定不会在右侧大端范围，只能是中间值位置或左侧小端范围，于是固定搜索范围右侧right=mid；若中间值小于目标，左边界肯定在右侧大端，而且可以缩小搜索范围为left = mid + 1；若中间值大于目标，左侧边界肯定在左边小端，而且可以缩小搜索范围为right = mid – 1，但是同时while (left < right)的结束条件是left = right，如果目标值比列表所有元素都小，最终会导致left=-1，发生越界，故这里应该写为left = mid，即right = mid – 1也是可以的，如果非要这么写，就需要处理临界值情况；

2.如果需要找不到目标值时返回-1，则可以修改最后的代码为：

//return left;
if (left == 0 && list.get(left)!=target){
    return -1;
}
return list.get(left) == target ? (left) : -1;

如果写为right = list.size() – 1 的方案B，也是可行的，需非常仔细观察与A的差异：

private static int left_bound_B(List<Integer> list,int target){
    int left = 0;
    int right = list.size() - 1; //差异
    while (left <= right){ //差异
        int mid = left + (right - left)/2;
        if (list.get(mid) == target){
            right = mid - 1; //差异
        }
        else if (list.get(mid) > target){
            right = mid - 1; //差异
        }else if (list.get(mid) < target){
            left = mid + 1;
        }
        System.out.println("left"+left);
        System.out.println("right"+right);
    }
    return left;
}

以上代码分析：初始化right = list.size() – 1，则循环条件应该写为while (left <= right)，因为while (left < right) 遗漏了left = right= list.size() – 1的临界值，且因为while (left <= right)的终止条件是left=right + 1，当二分匹配时，如果中间值等于目标值，则左侧边界肯定是目标值或者在左侧小端范围内，但同时为了使得循环能退出，故缩小右侧搜索范围为right = mid – 1，如果写为right = mid，则可知此时left = right=mid，不满足退出条件，并进入下一次循环，然后无限循环下去，即死循环了！如果中间值小于目标值，则左侧边界肯定是在右边大端范围内，同理，也是为了满足循环退出条件，缩小搜索范围为left = mid + 1；如果中间值大于目标值，分析类似，略！

如果需要找不到目标值返回 -1 ，则可以修改最后的返回值。这里需考虑临界值情况为：目标值比所有值都小，left=0，right=-1；目标值比所有值都大，left=list.size()，right=list.size()-1，故修改返回值为:

if (left == list.size() && list.get(left-1) != target){
    return  -1;
}
return left==0 && list.get(left) != target ? -1: left;

思考题：留个作业，写个右侧边界搜索算法，请看官思考一下吧！请不要只是脑海里闪过几行代码，那只能说明这个算法还在我这。

全文完！

我近期其他文章：

只写原创，敬请关注

vlambda博客
学习文章列表