在二分搜索中计算中点索引 [英] Calculating midpoint index in binary search

问题描述

因此，在二进制搜索中计算 mid 的正确方法是 mid = low + ((high - low)/2) 以处理溢出错误.

So, the correct way of calculating mid in a binary search is mid = low + ((high - low) / 2) in order to handle overflow errors.

我的实现使用了无符号的 64 位变量，而且我从未见过我的数组变得如此之大以至于导致溢出的情况.我还需要使用上面的实现还是可以使用 mid = (low + high)/2

My implementation uses unsigned 64 bit variables and I don't ever see a situation where my arrays get so big so as to cause an overflow. Do I still need use the above implementation or can I use mid = (low + high) / 2

这里的最佳做法是什么?

What's best practice here?

推荐答案

如果没有溢出的可能性，那么计算中点的溢出安全方法在技术上是不必要的:如果您愿意，可以使用不安全公式.但是，无论如何将它保留在那里可能是个好主意，以防有一天您的程序被修改以打破您的假设.我认为添加一条 CPU 指令使您的代码面向未来是对代码可维护性的一项重大投资.

If there is no possibility of overflow, the overflow-safe way of computing the midpoint is technically unnecessary: you can use the unsafe formula if you wish. However, it's probably a good idea to keep it there anyway, in case that your program gets modified some day to break your assumptions. I think that adding a single CPU instruction to make your code future-proof is a great investment in maintainability of your code.

这篇关于在二分搜索中计算中点索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！