问题标签 [binary-search]

每个程序员都被教导二进制搜索是搜索有序数据列表的一种很好、快速的方法。有很多使用二分搜索的玩具教科书示例，但在实际编程中呢：在实际程序中实际使用二分搜索在哪里？

有没有办法在 Javascript 中对文本文件中的特定键进行基于磁盘的二进制搜索？文本文件太大而无法加载到内存中，但按键值排序。特别是，我正在寻找一种在 Javascript中模仿 Perl 的Search::Dict功能的方法。

例如，如果我有一个文件 foo.txt：

look(c,foo.txt)c 5应该通过执行二进制搜索而不是线性遍历文件来返回行' '。

我已经使用 xpath 从 xml 文件填充了日期的排序列表（以 dd/mm/yyyy 格式存储为字符串）。

但是，当查询列表以查看列表中是否存在日期时，我总是得到否定的结果（即不存在），即使我已经硬编码查询字符串以匹配列表中的日期。

但是，在对包含查询字符串的索引进行字符串比较时，我得到 0 表示字符串是相同的。

什么会导致这种奇怪的行为？

按照这里的要求是代码

假期由以下人员组成：

搜索是：

返回以下 XML：

线性搜索和二分搜索有什么区别？

我正在努力将 Perl 程序移植到 Java，并在学习过程中学习 Java。原始程序的一个核心组件是一个Perl 模块，它使用二进制搜索在 +500 GB 排序的文本文件中进行字符串前缀查找（本质上，“寻找”到文件中间的字节偏移量，回溯到最近的换行符，比较带有搜索字符串的行前缀，“寻找”到该字节偏移量的一半/两倍，重复直到找到......）

我已经尝试了几种数据库解决方案，但发现在这种大小的数据集的绝对查找速度上没有什么比这更好的了。您知道任何现有的实现此类功能的 Java 库吗？如果做不到这一点，您能否指出一些在文本文件中进行随机访问读取的惯用示例代码？

或者，我不熟悉新的（？）Java I/O 库，但它是否可以选择对 500 GB 文本文件进行内存映射（我在 64 位机器上，有可用内存）并执行二进制搜索内存映射的字节数组？我很想听听您分享有关此问题和类似问题的任何经验。

我正在开发一个日志解析服务，用于捕获 Windows 事件日志中的特定安全事件。我最初的想法是使用 Microsoft 的LogParser，但除了选择预先已知的特定实例/事件 ID 之外，我并没有寻找任何功能。

经过一些基准测试后，我发现迭代整个 .NETEventLog.Entries集合在提取数据方面比查询 Microsoft 的 LogParser 快 3 倍多。

最终，要提取的数据将保存在 SQL Server 数据库中。由于该服务每天都会执行此任务，因此我希望避免重复条目，并且我需要一种方法来查找EventLog.Entries集合中尚未在数据库中的下一个条目。一旦找到初始条目，我就可以开始插入数据库。

我正要编写一个二分搜索，以使用DATETIME数据库中最新的时间戳字段来查找此条目，并将其与集合TimeWritten中某个项目的属性进行比较。EventLog.Entries我可以这样做，但我想知道是否已经有内置方法来执行此搜索？

第 2 栏（“啊哈！算法”）中的“编程珍珠”讨论了二分搜索如何帮助排序、树遍历等各种过程。但它提到二进制搜索可以用于“程序调试”。有人可以解释一下这是怎么做到的吗？

如果我有下表。

我将如何确保通过 :key 字段为二进制搜索优化存储行？

我将如何确保使用二进制搜索？

有没有办法在带有对象的 ArrayList 中实现二进制搜索？在此示例中，ArrayList 将使用字段“id”进行排序。

如果我应该使用二进制搜索返回具有指定 id 的用户，“User getUserById(ArrayList users, int userid)”会是什么样子？这甚至可能吗？

简单的问题 - 给出一个IList<T>如何在不自己编写方法并且不将数据复制到具有内置二进制搜索支持的类型的情况下执行二进制搜索的问题。我现在的状态如下。

• List<T>.BinarySearch()不是IList<T>
• 没有等效的ArrayList.Adapter()方法List<T>
• IList<T>不继承自IList，因此ArrayList.Adapter()无法使用

我倾向于认为使用内置方法是不可能的，但我无法相信 BCL/FCL 中缺少这种基本方法。

如果不可能，谁能给出最短、最快、最聪明或最漂亮的二分搜索实现IList<T>？

更新

我们都知道在使用二分搜索之前必须对列表进行排序，因此您可以假设它是。但我认为（但没有验证）排序是同样的问题 - 你如何排序IList<T>？

结论

似乎没有内置的二进制搜索IList<T>。可以使用LINQ 方法进行搜索和排序，但它可能会影响性能First()。OrderBy()自己实现它（作为扩展方法）似乎是你能做的最好的。