面试官,我会写二分查找法!对,没有 bug 的那种!

面试官,我会写二分查找法!对,没有 bug 的那种!

前言科普

第一篇二分搜索论文是 1946 年发表,然而第一个没有 bug 的二分查找法却是在 1962 年才出现,中间用了 16 年的时间。

2019 年的你,在面试的过程中能手写出没有 bug 的二分查找法么?

定义

在计算机科学中,二分查找(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法

搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;

如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空,则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找法代码

按照上面的定义,我们来尝试写一下二分查找法的代码。

public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            mid = (min + max) / 2;
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

现在问你,上面的代码有没有问题?哪段代码会出现 bug ?

请思考一分钟后再往下查看。

对于上面这段代码而言,问题出在第 6 行代码处:

mid = (min + max) / 2;

这句代码在 min 和 max 很大的时候,会出现溢出的情况,从而导致数组访问出错。

别看现在轻描淡写的指出了这个错误,但这个错误在当时可是存在了好些年。

那怎么改进呢?一般的做法是这样的:将加法变成减法。

public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            // 防止溢出
            mid =  min + (max - min) / 2;
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

还有一种更高逼格的写法,也是官方的二分搜索法的实现写法:使用 位运算

 public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            // 无符号位运算符的优先级较低,先括起来
            mid =  min + ((max - min) >>> 1);
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

希望通过今天的文章能帮助读者们在面试中手写对代码,毕竟,对于很多小公司来说,二分查找法是会出现在他们的笔试题中的。

如果你看过《编程珠玑》的话对本文肯定不陌生,如果你没看过,你可以点击下方去抽奖一波,小吴自费送书两本,希望大家喜欢~

点我抽奖!点我抽奖!点我抽奖!


大家五一劳动节 + 五四青年节,双节快乐!



推荐阅读

拜托,面试官别问我「布隆」了

有点难度,几道和「滑动窗口」有关的算法面试题

数据结构与算法:三十张图弄懂「图的两种遍历方式」

昨天,终于拿到了腾讯 offer

几道和「二叉树」有关的算法面试题

几道和散列(哈希)表有关的面试题

一道看完答案你会觉得很沙雕的「动态规划算法题」

几道和「堆栈、队列」有关的面试算法题

链表算法面试问题?看我就够了!


我就知道你在看!


本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 面试官,我会写二分查找法!对,没有 bug 的那种!

我还会在以下平台发布内容

GitHub 哔哩哔哩