算法细节系列（4）：二分查找总结

用户1147447

发布于 2019-05-26 09:58:52

8240

发布于 2019-05-26 09:58:52

文章被收录于专栏：机器学习入门机器学习入门

二分查找

刷题时，对二分查找的各种应用情况不太熟悉，严重影响了做题速度，特此总结下。在知乎上有一篇关于较全面的二叉查找，参考链接如下：【二分查找有几种写法？它们的区别是什么？】

分类

取整方式（2种）

- 向下取整
- 向上取整区间开闭（4种）

- 左闭右闭
- 左闭右开
- 左开右闭
- 左开右开问题类型（8种）

- 对于不下降序列a，求最小的i，使得`a[i] = key`
- 对于不下降序列a，求最大的i，使得`a[i] = key`
- 对于不下降序列a，求最小的i，使得`a[i] > key`
- 对于不下降序列a，求最大的i，使得`a[i] < key`
- 对于不上升序列a，求最小的i，使得`a[i] = key`
- 对于不上升序列a，求最大的i，使得`a[i] = key`
- 对于不上升序列a，求最小的i，使得`a[i] < key`
- 对于不上升序列a，求最大的i，使得`a[i] > key`

综上所述，二分查找共有 2×4×8=642 \times 4 \times 8 = 64种写法。接下来，我们就分别实现下，上述各种版本。

取整方式为向下取整

向下取整的核心代码为int mid = lf + (rt - lf) /2;，简单列一个表格，说明向下取整。

当数组长度为奇数的情况时:

index	0	1	2	3	4	5	6	7	8	9	10
len	1	2	3	4	5	6	7	8	9	10	11

int lf = 0, rt = len - 1;  // lf = 0, rt = 10
int mid = lf + (rt - lf) / 2; // mid = 5 整除

当数组长度为偶数的情况时:

index	0	1	2	3	4	5	6	7	8	9	10	11
len	1	2	3	4	5	6	7	8	9	10	11	12

int lf = 0, rt = len - 1;  // lf = 0, rt = 11
int mid = lf + (rt - lf) / 2; // mid = 5 向下取整

对于不下降序列a，求最小的i，使得ai = key

/**
     * 对于不下降序列a，求最小的i，使得a[i] = key
     * @param nums
     * @param key
     * @return
     */
    public int binarySearch_1(int[] nums,int key){

        int lf = 0, rt = nums.length-1; //闭区间 [0,len-1]

        while (lf < rt){
            int mid = lf + (rt-lf) / 2;

            if(nums[mid] < key){
                lf = mid + 1;
            }
            else{
                rt = mid;
            }
        }

        if (nums[rt] == key) return rt;

        return -1;
    }

测试结果：

非重复元素

        int[] nums = {1,2,3,4,5,6,7,8,9,10};
        for (int i = 0; i < nums.length; i++){
            System.out.print(bs.binarySearch_1(nums,nums[i]) + "  ");
        }
        int NONE = -1;
        System.out.println(bs.binarySearch_1(nums,NONE));

输出：
0  1  2  3  4  5  6  7  8  9  -1

重复元素

// 重复元素
        int[] nums_repeated = {1,2,3,4,5,5,6,6,7,8,9,10};
        for (int i = 0; i < nums_repeated.length; i++){
            System.out.print(bs.binarySearch_1(nums_repeated,nums_repeated[i]) + "  ");
        }
        System.out.println(bs.binarySearch_1(nums,NONE));
输出：
0  1  2  3  4  4  6  6  8  9  10  11  -1

为什么是lf < rt，能不能lf <= rt？不能，注意while循环中的判断语句，砍掉的元素一定是小于key的，如果元素不重复好办，当小于key的元素坎完后，就可以接着坎key的右半部分，由向下取整决定，每当坎一次右，rt向左移动一格，直到lf == rt，此时必须跳出循环，如果改成 lf <= rt，那么必然会进入死循环。
while循环外部为什么还需要判断一次？小于key的左半部分一定是被砍掉的，但while循环中被砍掉最后一个元素跳出循环后，它可能有两种情况，key 和比key大的值，所以必须进行一次判断。

对于不下降序列a，求最小的i，使得ai > key

/**
     * 对于不下降序列a，求最小的i，使得a[i] > key
     * @param nums
     * @param key
     * @return
     */
    public int binarySearch_2(int[] nums, int key){
        int lf = 0, rt = nums.length-1; //闭区间

        while (lf < rt){

            int mid = lf + (rt - lf) / 2; //向下取整

            if (nums[mid] <= key){
                lf = mid + 1;
            }else{
                rt = mid;
            }
        }

        if (nums[rt] > key) return rt;

        return -1;
    }

测试结果：

// 对于不下降序列a，求最小的i，使得a[i] > key
        int[] nums_2 = {1,2,3,4,5,6,7,8,9,10};
        for(int i = 0; i < nums_2.length; i++){
            System.out.print(bs.binarySearch_2(nums_2, nums_2[i]) + "  ");
        }

输出：
1  2  3  4  5  6  7  8  9  -1

循环外的if语句是否可以去掉，直接返回rt？你可以试试，用我的测试用例重新跑一下，你就发现问题了。这里就是为了防止边界条件而进行的约束，假设lf在不断更新，导致的一个结果就是它将不断靠近rt而rt始终没有变化，此处如果遍历到数组末端那个元素，它会同样跳出循环，而让它跳出的是while循环中的if语句，而非else，所以while循环的判断语句是为了规避这种特殊情况。

取整方式为向上取整

向下取整的核心代码为int mid = lf + (rt + 1 - lf) /2;，简单列一个表格，说明向上取整。

当数组长度为奇数的情况时:

index	0	1	2	3	4	5	6	7	8	9	10
len	1	2	3	4	5	6	7	8	9	10	11

int lf = 0, rt = len - 1;  // lf = 0, rt = 10
int mid = lf + (rt + 1 - lf) / 2; // mid = 5 不影响

当数组长度为偶数的情况时:

index	0	1	2	3	4	5	6	7	8	9	10	11
len	1	2	3	4	5	6	7	8	9	10	11	12

int lf = 0, rt = len - 1;  // lf = 0, rt = 11
int mid = lf + (rt +　1 - lf) / 2; // mid = 6 向上取整

对于不下降序列a，求最大的i，使得ai = key

此处和向下取整，求最小的i是一个完美对偶关系，显然用向上取整的方式更容易实现，代码如下。

/**
     * 对于不下降序列a，求最大的i，使得a[i] = key
     * @param nums
     * @param key
     * @return
     */
    public int binarySearch_3(int[] nums, int key){

        int lf = 0, rt = nums.length-1;

        while (lf < rt){
            int mid = lf + (rt + 1 - lf) / 2;

            if (nums[mid] > key){
                rt = mid -1;
            }else{
                lf = mid;
            }

        }

        if(nums[lf] == key) return lf;

        return -1;
    }

测试结果：

非重复元素

// 非重复元素
        for (int i = 0; i < nums.length; i++){
            System.out.print(bs.binarySearch_3(nums,nums[i]) + "  ");
        }
        System.out.println(bs.binarySearch_3(nums,NONE));
输出：
0  1  2  3  4  5  6  7  8  9  -1

重复元素

// 重复元素
        for (int i = 0; i < nums_repeated.length; i++){
            System.out.print(bs.binarySearch_3(nums_repeated,nums_repeated[i]) + "  ");
        }
        System.out.println(bs.binarySearch_3(nums,NONE));

输出：
0  1  2  3  5  5  7  7  8  9  10  11  -1

是不是很有爱，向上取整能够取重复元素的最大下标！而且代码形式和向下取整的最小i完美对称。

同样的，因为while循环中的主要变动在于rt指针，把所有大于key的元素全部砍掉，而一旦所有元素符合小于等于key的条件时，由于向上取整的好处，lf指针也会慢慢向rt靠近，所以针对重复元素它选取的一定是最大下标。

对于不下降序列a，求最大的i，使得ai < key

/**
     * 对于不下降序列a，求最大的i，使得a[i] < key
     * @param nums
     * @param key
     * @return
     */
    public int binarySearch_4(int[] nums, int key){
        int lf = 0, rt = nums.length-1;

        while (lf < rt){

            int mid = lf + (rt + 1 - lf) / 2;

            if (nums[mid] >= key){
                rt = mid - 1;
            }else{
                lf = mid;
            }
        }

        if (nums[lf] < key) return lf;

        return -1;
    }

测试结果：

// 对于不下降序列a，求最大的i，使得a[i] < key
        for(int i = 0; i < nums_2.length; i++){
            System.out.print(bs.binarySearch_4(nums_2, nums_2[i]) + "  ");
        }
输出：
-1  0  1  2  3  4  5  6  7  8

和向下取整求最小的i，一个道理，最坏情况rt不断递减地靠近lf，此时对于第一个元素会存在漏检的情况，所以最后要加一个边界条件。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017年04月05日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

腾讯云测试服务

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

腾讯云测试服务

登录后参与评论

0 条评论

热度