此篇文章同时发布在知乎专栏 前端后端客户端,专栏专注于前端、后端、客户端开发的技术分享与探讨,欢迎关注。

最近在刷 LeetCode 的过程中遇到许多 二分查找 的问题。

在计算中间值下标 mid 时,我是这样写的:

1
mid = (left + right) // 2

后面在评论中看了一些其他大佬的题解,发现大家都是这样写的:

1
mid = left + (right - left) // 2

下面就来探究一下为什么 mid = (left + right) // 2 的写法是错误的。

int 类型

int 是一种数据类型,用于定义整数类型变量的标识符,是带符号整数。

在现在对计算机中,int 占用 4 字节,32 比特,数据范围为:-2147483648 ~ 2147483647 [-2^31 ~ 2^31-1]

那么对于两个都接近 2147483647 的数字而言,它们相加的结果将会溢出,变成负数。

所以,为了避免溢出情况的发生,我们不能使用 mid = (left + right) // 2 来计算 mid 值,而是使用 mid = left + (right - left) // 2 来作为替代。

对 Python 而言

然而对 Python 来说,这种溢出情况是不会发生的。

在 Python2.7 版本中存在 intlong 两个数据类型存储整数,当 int 存在溢出情况时,Python 将会把数转为 long 类型,避免了溢出情况的发生。

在 Python3 中,就只剩下一个可以任意放大的 int 类型了,也不存在整型溢出的情况啦。

所以在 Python 中想要 mid = (left + right) // 2 这样写也是没啥问题的。

二分查找题

最后扔几题二分查找相关的题目给大家练练手~

推荐阅读