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

叁歲伎倆 2022-02-05 06:29 82阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

### 前言科普 ###

第一篇二分搜索论文是 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;
        }

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

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

**点我抽奖！点我抽奖！点我抽奖！**

**大家五一劳动节 + 五四青年节，双节快乐！**

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 1]

[有点难度，几道和「滑动窗口」有关的算法面试题][Link 2]

[数据结构与算法：三十张图弄懂「图的两种遍历方式」][Link 3]

[昨天，终于拿到了腾讯 offer][offer]

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

[几道和散列（哈希）表有关的面试题][Link 5]

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

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

[链表算法面试问题？看我就够了！][Link 8]

我就知道你在看！

[640_wx_fmt_jpeg]: /images/20220205/80ef8c82e1724676af221e3e324411ea.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485197&idx=1&sn=1bbd40d49adb09875fd324664bd5bc8b&chksm=fa0e688ccd79e19a36599b53e4a8acf9a725ace3f6df28925075ff25778238471a283f0f8e1f&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485076&idx=1&sn=ba747d1efd4c009da83681a6bb4ff549&chksm=fa0e6915cd79e003249e9ee045d09a174b0e5aff2a6ecd807e10fd01bfbc1a37da688eb51637&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 8]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect