问题标签 [binary-search]

这个想法是使用多个数组，每个数组长度为 2^k，根据 n 的二进制表示来存储 n 个元素。每个数组都是排序的，不同的数组不以任何方式排序。

在上述数据结构中，SEARCH 是通过对每个数组进行一系列二分查找来执行的。INSERT 通过一系列相同长度的数组合并执行，直到到达一个空数组。

更多细节：假设我们有一个长度为 2^k 的垂直数组，并且该数组的每个节点都附有长度为 2^k 的水平数组。

即垂直数组的第一个节点连接一个长度为2^0=1的水平数组，垂直数组的第二个节点连接一个长度为2^1=2的水平数组，以此类推。所以插入首先在第一个水平数组中执行，对于第二次插入，第一个数组变为空，第二个水平数组充满 2 个元素，第三次插入第一个和第二个数组水平。数组被填充等等。我为搜索和插入实现了正常的二进制搜索，如下所示：

谁能建议如何修改这个程序或一个新程序来实现如上所述的动态二进制搜索！

是否有一个库可用于在非常大的文本文件（可以是 10GB）中执行二进制搜索。

该文件是一种日志文件 - 每行都以日期和时间开头。因此行是有序的。

为二分搜索创建一个递归函数。
这个函数接受一个排序数组和一个要搜索的项目，并返回项目的索引（如果项目在数组中），或者返回-1（如果项目不在数组中）。
此外，编写一个测试程序来测试您的功能。

http://en.wikipedia.org/wiki/Binary_search_algorithm#Average_performance

如果我要查找的整数始终在数组中，有人可以帮我编写一个可以计算二进制搜索算法平均性能的程序吗？

编辑：我知道我可以通过实际运行程序并计算调用次数来做到这一点，但我在这里要做的是在不调用函数的情况下做到这一点。

编辑2：KennyTM：这是一个时间复杂度，我正在尝试计算平均调用次数。例如，在 A[2] 中查找整数的平均调用次数为 1.67 (5/3)

问题：

我为此使用 Java Tutorials™</a> 源代码。这是源代码。

我试过这个：

它工作得很好。但是，当我使用这个时：

它确实会在我键入时显示dce_iface，dce但是当我键入时_，o它s会显示其他内容dce_offset，例如偏移量来自words.add("fragoffset");列表中的某个位置。

我能做些什么来解决这个问题？先感谢您。

我有一个旋转的排序列表，并希望对该列表进行二进制搜索以找到最小元素。

让我们假设初始列表是 {1,2,3,4,5,6,7,8} 旋转列表可以像 {5,6,7,8,1,2,3,4}

在这种情况下，正常的二进制搜索不起作用。任何想法如何做到这一点。

- 编辑

我还有另一个条件。如果列表没有排序怎么办？

我有一个较大的字符串数组，我想用作查找。

我正在使用in_array()，但我怀疑它做了一个简单的循环 - 有谁知道in_array()算法是否使用 bsearch 算法？

我们希望在复杂度不大于 的循环排序数组中搜索给定元素O(log n)。示例：在 中
搜索。 13{5,9,13,1,3}

我的想法是将循环数组转换为常规排序数组，然后对结果数组进行二进制搜索，但我的问题是我提出的算法很愚蠢，它O(n)在最坏的情况下采用：

那么第i个元素的对应索引将由以下关系确定：

很明显，我的转换（从循环到常规）算法可能需要 O(n)，所以我们需要一个更好的。

根据 ire_and_curses 的想法，这里是 Java 中的解决方案：

希望这会奏效。

我有一棵红黑树，基本操作插入、删除、遍历中序、后序和预序等。

我希望创建一个可以返回树中大于指定值的节点的方法。小于也一样。

任何人都可以指出一些伪代码/算法（它们可能意味着同样的事情）

干杯

我正在尝试创建包含两个 int 值和一个按字典顺序排序的字符串值的二叉树，但我不知道该怎么做。我创建了一个已经排序的数组列表，但是二叉树必须是基于引用的，未排序，我正在考虑在创建列表时对其进行排序。有人能帮忙吗？任何简短的想法将不胜感激。