有哪些事实没有一定计算机知识的人不会相信？

向右看齐 2023-01-06 05:35 39阅读 0赞

![format_png][]

昨天在知乎看到一个热门话题：**有哪些事实没有一定计算机知识的人不会相信？**

![format_png 1][]

我抖了一个机灵，把《编程珠玑》上关于二分查找法的梗答上去，一天之内挺多人留言点赞说**没想到自己写不出完全准确的二分查找法，小丑竟然是我自己**，根据评论数据来看，的的确确是九成的人无法写对，他们通过这个回答知道了自己以为知道但实际上不不知道的东西。

![format_png 2][]

我觉得这个小知识或许对你有帮助，所以分享一下。

以下为我在该问题下的回答:

别说是没有计算机知识的人了，即使有也很多人不相信：**给予他们充足时间的情况下，有百分之九十以上的人无法编写出完全准确的二分查找法的代码。**

以上的结论来源于《编程珠玑》一书。

如果不信的话，可以先自己手写一遍，不想写的话，看看下方的代码，然后花一分钟思考，你觉得它哪里有问题？

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;
     }

看出来了么？

揭晓答案，问题出在第 6 行代码处：

`mid = (min + max) / 2;`

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

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

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

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

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;
    }

--------------------

今天是持续写作第 **12** / 100 天。

如果你有想交流的话题，欢迎留言。

![format_png 3][]

[format_png]: /images/20221119/9d4d923440ba41729bedf81160f23953.png
[format_png 1]: /images/20221119/cdeab1d7299e42d5a4d2159a8b0009de.png
[format_png 2]: /images/20221119/cf5220906aa84ced94a523f5b0cbb1bb.png
[format_png 3]: /images/20221119/f0d61acb1bd748638d3a026247f2a6cf.png