问题标签 [binary-search]

我有一个二进制搜索循环，它在执行路径中被多次命中。

分析器显示搜索的除法部分（根据搜索范围的高和低索引查找中间索引）实际上是搜索成本最高的部分，大约是 4 倍。

（我认为）对于有效的二分搜索来说，找到精确的中间值并不重要，只是靠近中间的一个值，在任何一个方向上都没有偏差。

是否有一种比特旋转算法可以用mid = (low + high) / 2更快的东西代替？

编辑：语言是 C#，但等效的位操作在任何语言中都有效（尽管它可能对性能没有好处），这就是我关闭 C# 标记的原因。

我有一个类和实例列表，看起来像这样（更改了字段名称以保护无辜/专有）：

该列表bloatList由内部保存BloatProducer并以这样的方式维护：它只附加新Bloat记录，不修改任何旧记录，并且每个字段都是单调递增的，例如bloatProducer.testMonotonicity()总是返回true。

我想使用timeInMilliseconds、spaceInBytes 或 costInPennies 字段Collections.binarySearch(list,key,comparator)来搜索记录。Bloat（如果数字在两条记录之间，我想找到上一条记录）

编写一系列 3 个比较器类以使其工作的最简单方法是什么？我是否必须使用带有虚拟字段的 Bloat 对象作为我不搜索的键？

我正在解决 sphere 的在线判断最短路径问题。这段代码给我带来了麻烦：

我怎样才能避免这种情况NullPointerException？

输入文件：

我有两个系列，每个系列包含大约 40,000 件物品。

列表 2 中的元素通过外键链接到列表 1 中的元素。

对于列表一的每个元素，我想在列表二中找到相应的元素。

像这样的东西：

这行得通，但速度很慢。

现在，list1 和 list 2 都按数据库中的这些键排序。所以 list1 按 ChildID 排序， list2 按 ID 排序（相同的值）。

我认为二进制搜索会大大加快这一速度，但我在某处读到 Linq 会为 Where 子句中的列表选择最合适的策略。也许我需要明确地转换为排序列表？或者也许我需要使用比较器实现自定义二进制搜索算法？

任何见解都值得赞赏。

谢谢。

我有一个字典列表，如下所示：

dict 项根据'offset'数据在列表中排序。真实数据可能更长。

我想要做的是在给定特定偏移值的列表中查找一个项目，该偏移值不完全是这些值之一，而是在该范围内。所以，二进制搜索是我想要做的。

我现在知道 Pythonbisect模块，它是一个现成的二进制搜索——很好，但不能直接用于这种情况。我只是想知道适应bisect我需求的最简单方法是什么。这是我想出的：

它打印：

我的问题是，这是做我想做的最好的方法，还是有其他更简单、更好的方法？

这一直困扰着我一段时间。我知道给定 N 个键以二叉搜索树的形式排列，可以创建的树的可能数量对应于Catalan 序列中的第 N 个数。

我一直在试图确定这是为什么；找不到任何甚至可能试图直观地解释它的东西，我求助于 SO 的集体知识。我找到了其他方法来计算可能的树的数量，但它们似乎不太直观，除了如何使用它之外没有提供任何解释。再加上 wiki 页面（上面的链接）甚至显示了带有 3 个键的可能的树形结构的图像，这让我认为有一个很好的和简洁的解释可以听到（不用说，不包括在文章中）。

提前致谢！

我有字符串数组 [1, 2, 3]，我使用 Arrays.binarySearch 搜索所有这些数字，它找到 1 和 2，但使用 3 它返回 -1。知道为什么它会这样工作吗？在数组/集合中始终工作搜索有什么更好的选择？

所以，我想更多地了解二进制搜索，因为我不太明白。二进制搜索需要一个先决条件，即数组已排序。我说对了吗？似乎一个方法应该检查这个前提条件，如果不满足就抛出异常。但是，为什么检查前提条件是个坏主意？

这是 中描述的问题Programming pearls。我无法理解作者描述的二进制搜索方法。谁能帮忙详细说明一下？谢谢。

编辑：我一般可以理解二进制搜索。我只是不明白如何在这种特殊情况下应用二进制搜索。如何确定丢失的数字是否在某个范围内，以便我们可以选择另一个。英语不是我的母语，这也是我不能很好理解作者的原因之一。所以，请使用简单的英语:)

编辑：谢谢大家的精彩回答和评论！我从解决这个问题中学到的最重要的一课是二进制搜索不仅适用于排序数组！

我需要一个内存块的比较函数，以便在 D 编程语言中对字节数组进行二进制搜索。它不需要任何有用的语义。它只需要快速并且是有效的比较函数（产生总排序的函数）。已知要比较的内存块具有相同的长度。

Cmemcmp实际上很慢，因为它试图保留有用的字符串比较语义，而我不需要。以下是迄今为止我想出的最好的。有没有人知道更好的东西，最好不要浸入非便携式 CPU 特定指令？

编辑：我已经阅读了 SSE，我不想使用它有 3 个原因：

1. 它不是便携式的。
2. 它需要在 ASM 中编程。
3. 比较说明假定您的数据是浮点数，如果某些数据恰好与 NaN 的模式匹配，这可能会出现问题。