问题标签 [binary-search]

是否有一个库函数对列表/元组执行二进制搜索，如果找到则返回项目的位置，如果没有则返回“假”（-1、无等）？

我在bisect 模块中找到了 bisect_left/right 函数，但即使项目不在列表中，它们仍然返回一个位置。这对于他们的预期用途来说非常好，但我只想知道一个项目是否在列表中（不想插入任何东西）。

我想过使用bisect_left然后检查该位置的项目是否等于我正在搜索的项目，但这似乎很麻烦（而且我还需要检查该数字是否可以大于我列表中的最大数字）。如果有更好的方法我想知道。

编辑澄清我需要这个：我知道字典非常适​​合这个，但我试图保持内存消耗尽可能低。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够根据它们的索引访问这些值。如果该值不在列表中，我还希望能够找到特定值的索引或 None 。

为此使用字典将是最快的方法，但会（大约）使内存需求增加一倍。

我在问这个问题时认为我可能忽略了 Python 库中的某些内容。正如 Moe 建议的那样，我似乎必须编写自己的代码。

想象一下，您每天都会收到一位作者的新书。这本书正在进行中。他没有告诉你他改变或增加了什么。

您的工作是识别更改和添加内容，并仅将它们传递给出版商（他们没有时间每天阅读整本书）

出于这个问题的目的，这本书由 1m 行的 ascii 文本组成，并且还在不断增长（实际上是一个 MySQL 备份文件）。

我目前的想法是对每行（1k 个字符）进行安全哈希（例如 SHA256）并将其存储在 HD 上。由于散列只有 32 字节，因此文件只有 32MB。

然后当我们明天得到下一个文件时，我们逐行检查它，为每一行创建一个新的散列，并将其与前一天的散列进行比较。

当该过程完成后，我们会覆盖为第二天准备的哈希文件。

比较使用字符串比较（ > < 操作数）的二进制搜索方法，这将返回平均四次迭代的结果。

我还没有编写 btree 索引解决方案，但你将如何解决这个问题？

我将如何仅使用数组来实现二进制搜索？

我正在写一个键记录查找我在键和记录号之间有一个索引的位置。这是按键排序的。有没有比我在速度优化方面做得更好的方法？

当给定一组静态对象（从某种意义上说是静态的，一旦加载它就很少改变），需要以最佳性能重复并发查找，哪个更好，HashMap或者使用一些自定义比较器进行二进制搜索的数组？

答案是对象还是结构类型的函数？散列和/或相等的函数性能？哈希唯一性？列表大小？ Hashset尺寸/设置尺寸？

我正在查看的集合的大小可以从 500k 到 10m 不等——以防该信息有用。

虽然我正在寻找 C# 答案，但我认为真正的数学答案不在于语言，所以我不包括那个标签。但是，如果需要注意 C# 特定的事情，则需要该信息。

我有一个节点结构

在一个排序的向量中。

我想知道算法中是否有一个函数可以对向量进行二进制搜索并找到一个元素。

我需要一个与 C++ STL 容器兼容的二进制搜索算法，类似于std::binary_search标准库的<algorithm>标头中的内容，但我需要它返回指向结果的迭代器，而不是告诉我元素是否存在的简单布尔值。

（顺便说一句，标准委员会在为 binary_search 定义 API 时到底在想什么？！）

我主要关心的是我需要二进制搜索的速度，所以虽然我可以使用其他算法找到数据，如下所述，但我想利用我的数据已排序的事实来获得二进制的好处搜索，而不是线性搜索。

到目前为止lower_bound，upper_bound如果缺少基准，则失败：

注意：只要它与容器兼容，我也可以使用不属于 std 命名空间的算法。比如说，boost::binary_search。

我有一个 5000 个整数的排序数组。我能以多快的速度判断一个随机整数是否是数组的成员？一般来说，C 和 Ruby 的答案会很好。

数组值的形式为

其中c可以是 1 到 5000 之间的任何整数。

例如：

二进制搜索比看起来更难实现。“虽然二分搜索的基本思想相对简单，但细节却出奇地棘手……”——唐纳德·克努斯。

哪些错误最有可能被引入到新的二分搜索实现中？

首先：我不是程序员，从未学过编程/算法。实际上我必须编程，主要是在 awk 或 ruby​​ 中，一些 bash。

在今天的任务中，我在纯文本文件中有一个巨大的数据集（浮点数），一个记录/行，以及集合中所有数字的总和，但是总和是错误的，因为有些数字（只能一）在集合中是负数，但我们在文件中看不到它（如果元素是负数，则没有符号）。

但我必须找到它/他们：所以首先我计算了正确的总和（将所有数字与 相加awk）并不关心他们的迹象。现在我现在是原始总和（关心符号）和我的新总和之间的差异。但我必须找到数据集的所有子集，它们的和与差/2 完全相同。

例如：

现在我们可以计算 1+2+3+4+5 - ORIG SUM 之间的差值：15-5=10。10/2 = 5，所以我需要找到所有可以加起来为5的子集，即[1,4]，[2,3]，[5]。

有正确的方法吗？我更喜欢 awk、ruby、shell 脚本，但 python 和 perl 都是可以接受的（没有大量使用外部库，因为我无权安装它们）。

提前致谢。