问题标签 [binary-search]

这是G. Michael Scneider 和 Judith L. Gersting的教科书Invitation to Computer Science的直接引述。

在第 3.4.2 节的末尾，我们讨论了在未排序列表上使用顺序搜索与排序列表然后使用二分搜索之间的权衡。如果列表大小为 n=100,000，则在第二个备选方案在比较次数方面更好之前，必须进行多少次最坏情况搜索？

我真的不明白这个问题在问什么。

顺序搜索是有序的（n），二进制是有序的（lgn），在任何情况下lgn总是小于n。在这种情况下，n 已经给出，所以我应该找到什么。

这是我的家庭作业之一，但我真的不知道该怎么做。谁能用简单的英语为我解释这个问题？

顶部列出的 binary_search 函数有问题。不知道该去哪里。我对二进制搜索不是很熟悉。

完成后，程序假设从文件中获取输入，将其分配给数组，然后对数组进行排序。在此之后，我需要使用二进制搜索来查找用户给出的数字并将其在数组中的位置显示给用户。

更新：为找到的索引获取错误的输出....我应该只在 midindex 中添加一个吗？

我正在尝试使用objective-c 块实现二进制搜索。我正在使用该功能indexOfObject:inSortedRange:options:usingComparator:。这是一个例子。

我想知道如何将外部定义的 Objective-c 块与上述功能一起使用。这里有两个比较函数。

这些是参考以下声明编写的，这些声明可以在NSObjCRuntime.h.

有没有比二分搜索更快的算法来搜索数组的排序值？

就我而言，我在一个数组中有一个排序值（可以是任何类型的值），如果我正在寻找的值在范围内A，我需要返回nA[n] and A[n+1]

我有一个文件，每行包含int;int值。两列都是逐行升序的。我计划使用以下代码将该文件加载到数组中：

我打算使用这个数组根据键 $tmp[0] 进行二进制搜索。数组将有 1000 个元素，但搜索将应用于 10.000 个不同的值。我应该简单地定义一个 2x1000 矩阵并将元素加载到其中吗？

谢谢

我想找到正弦函数的零点。参数是一个区间 [a,b]。我必须类似于二进制搜索。

实现一个函数，在 a 和 b 之间的区间内搜索 sinus 函数中的空点。search-interval[lower limit, upper limit] 应该减半，直到下限和上限之间的距离小于 0.0001。

这是我的代码：

它给了我很多错误return zeropoint(middle,b);

在第一步中，我只想找到区间中的第一个零点。

有任何想法吗？

是否有类似于内置 bsearch 的东西，如果相同的元素不存在，则返回立即较小的元素，仅当元素已经小于所有其他元素时返回 NULL。这将要求用户检查返回值的键是否与函数参数相同，但它本身就非常有用。谢谢。

我想获取我正在测试的元素的迭代器 in binary-search。但它只返回一个bool指示它是否找到该值。如何获取迭代器？

最近我听到一个观点，二进制搜索可以通过将范围划分为 phi（黄金比例）而不是 2 来改进。这对我来说是一个很大的惊喜，因为我从未听说过这种优化。这是真的？如果除以 2 和除以 phi 的性能相同，这会是真的吗？

如果不是，是否存在黄金分割搜索比二分搜索执行得更快的一般条件？

UPD：已编辑以删除不相关的 Wikipedia 文章的链接。抱歉误导。

我有兴趣有效地跟踪整数格上的大盒子的质心，从该格子中反复雕刻出正交形状的区域。我一直在研究计算几何文献，并且有多种可能相关的数据结构，但大部分讨论都是关于可见性计算（用于计算机图形学）或最近邻查找（用于数据挖掘等）。

论文 http://www.graphicsinterface.org/pre1996/92-NaylorSolidGeometry.pdf，即：

讨论了一个通过“二元空间划分树”表示几何对象的系统，支持集合操作，并且有趣地提到（没有细节）在集合操作之后重新计算对象的质心。也许我有一个盲点，但是在树合并算法期间如何有效地更新质心对我来说并不是很明显，而且我还没有在引用 Naylor 的论文中找到关于质心计算的讨论。任何指针？