什么是执行二进制搜索的陷阱？ [英] What are the pitfalls in implementing binary search?

问题描述

二进制搜索是很难实现比它的外观。 虽然二进制搜索的基本思想是比较直观，细节更是出奇地棘手...... - 高德纳

Binary search is harder to implement than it looks. "Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…" — Donald Knuth.

哪些错误是最有可能被引入到一个新的二进制搜索执行？

Which bugs are most likely to be introduced into a new binary search implementation?

推荐答案

下面是一些我能想到的：

Here are some I can think of:

• 关闭接一个错误，决定下一区间的边界时
• 处理重复项，如果你想返回数组中的第一个平等项目，而是返回随后等于项目
• 数值下溢/溢的计算指标，以巨大的数组时
• 递归的 VS 的非递归的实施，一个设计选择，你应该考虑

• Off-by-one errors, when determining the boundary of the next interval
• Handling of duplicate items, if you are suppose to return the first equal item in the array but instead returned a subsequent equal item
• Numerical underflows/overflows when computing indices, with huge arrays
• Recursive vs non-recursive implementation, a design choice you should consider

难道这些你有什么想法？

Are these what you have in mind?

这篇关于什么是执行二进制搜索的陷阱？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！