问题标签 [binary-search]

我有一些存储在排序向量中的数据。该向量按某个键排序。我知道 STL 有一个算法来检查一个元素是否在这个排序列表中。这意味着我可以写这样的东西：

但是我发现“thingToSearchFor”对象的构造不优雅。有没有更好的办法？类似的东西？

我正在尝试在 Python 中编写一个函数，该函数在排序列表中找到大于我作为参数传入的特定值的第一个数字。我在网上找到了使用简单列表推导来实现此目的的示例，但出于我的目的，我需要经常在大型列表上执行此操作，因此在线性时间内运行的搜索成本太高。

尽管我遇到了一些无法正常工作的边缘情况，但我在编写类似迭代二进制搜索的函数来实现这一点方面已经有了突破。顺便说一句，该函数不需要处理列表中没有更大项目的情况。这是我现有的功能：

我注意到此功能不起作用的一种情况如下：

这里正确的结果是262140，因为这是列表中大于 的第一个数字262139。

任何人都可以推荐一个更干净的实现吗？我不认为这会是一个如此深奥的问题，尽管到目前为止我还没有在任何地方找到解决方案。

我总是得到-3。问题在"Name". "Name"为什么我的数组中不能有？任何的想法？

我编写了以下代码来对target列表或元组中的值 进行二进制搜索collection。

如您所见，当在target中找不到时collection，该函数返回-1。不管我做了什么，函数都返回-1。

是什么导致了这个问题？

在我的 Android 应用程序中，我想要一个带有自动完成功能的输入字段。项目数约为 300000。最好的解决方案似乎是将项目放入一个文件（在 sdcard 上），每行一个项目，每行具有相同数量的字符，以便我可以寻找特定的行号. 如果用户在文本字段中输入内容，我将二进制搜索（通过 RandomAccessFile）文件并显示建议。

我希望自动完成速度非常快（最好在 100 毫秒以下，但我想这是不可能的），我可以做哪些优化？

更新 1： 我会将用户输入转换为带空格的小写英文字符 (az)。所以 'A/b' 会被转换成 'a b' 然后被搜索。

Uodate 2： 我现在意识到我需要额外的东西 - 搜索以单词开头的子字符串。

我需要帮助编写一个使用二进制搜索递归计算输入非负整数的平方根（向下舍入到最接近的整数）的程序。

这是我到目前为止所拥有的：

它必须使用二进制搜索来计算平方根这一事实让我感到困惑。如果有人对如何做到这一点有任何建议，将不胜感激。谢谢

-这是我使用二分搜索算法的 find() 方法：

• 它就像您期望的那样工作。完全没有问题。

  /li>

这是使用线性搜索的原始 insert() 方法。很简单，对吧？

我需要修改 insert() 方法以使用 find() 方法的二进制搜索算法。到目前为止，这是我想出的。显然它有问题，但我似乎无法找到问题所在。它根本不起作用，即不执行插入：

语言：Java

使用有序数组。

我有一个这样的容器：

现在，如果我想在 time 之前获取最后一个数据对象t，我可以创建一个虚拟对象并调用upper_bound()：

这给了我对数搜索的复杂性。
除了看起来笨拙之外，如果这样的虚拟对象很难创建（不是运行时性能，而是编码工作），这种方法是有问题的。

我看过std::multiset::key_comp但我不知道如何使用它。
两者都std::multiset::find()希望std::binary_search()我给他们容器key_type，即TimeSortableData对象...

如何在无需创建虚拟对象的情况下进行有效搜索？

评论更新：
还有find_if()：它可以让我省去创建虚拟对象的工作，但代价是 O(n) 复杂性。

以下代码有什么问题？为什么它没有使用我的二进制搜索实现找到字母？

我想在 Perl 中实现一个二进制搜索算法。我的“数组”按降序排序（不是实际的数组，而是一个获取索引并返回值的函数）。问题是可能存在相同值的延伸。如果我的搜索值处于这样的范围内，我想返回包含它的第一个索引。

这是我写的：

这是一个使用它的简单示例：

问题是我不确定我的最后一个 else （标有## SEE MY QUESTION BELOW ##）是否“漂亮”。有没有更好的方法来做到这一点？