面试官，我会写二分查找法！对，没有 bug 的那种！
16lz
2021-01-22
前言科普
第一篇二分搜索论文是 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;
}
希望通过今天的文章能帮助读者们在面试中手写对代码，毕竟，对于很多小公司来说，二分查找法是会出现在他们的笔试题中的。
更多相关文章
- 前 K 个高频元素告诉你桶排序有啥用
- Hard 级别难度？桶排序几行代码搞定！
- 推荐一个项目：数据结构和算法必知必会的 50 个代码实现
- 十大经典排序算法动画与解析，看我就够了！（配代码完全版）
- 深度好文 ｜Matplotlib 可视化最有价值的 50 个图表（附完整 Python
- 阅读优秀 Python 开源项目的代码，提升编程技能（GitHub 资源帖推荐）
- 两行代码搞定：Jupyter Notebook中自动补全代码
- 世界杯：用Python分析热门夺冠球队-(附源代码)
- 官方示例（十三）：3步70行代码开发GIS点坐标技术 ThingJS