问题标签 [binary-search]

我有一个函数，binary_range_search它是这样调用的：

brs_iterator->()将遍历 $range 重叠的所有 @$ranges。

我想扩展binary_range_search以能够以多个范围作为目标来调用它，例如：

因此，当对 $range->[0] 的搜索用尽时，它应该转到 $range->[1]，以此类推。以下是原始形式的相关函数：

这是一种标准的二分搜索策略，直到找到重叠范围。然后它向右移动，耗尽它，向左移动，耗尽它，最后放弃。理想情况下，它应该可能shift是下一个目标范围，并重做搜索，我想（也许通过递归？）。我的问题是，我不确定如何使用迭代器构造来实现它。

是否有必要使用键和值来实现BST ？我可以实现一个具有如下方法调用的 BST，其中它将根据 V 值在每个节点上进行遍历是应该去左节点还是右节点的比较：

或者，我可以实现BST，使其具有如下方法调用，其中K键是比较确定是遍历左节点还是右节点：

我有一个浏览器部署的 Flash 应用程序（不是一个可以访问 SQLConnection 的 AIR 应用程序），它通过 HTTPService 从远程服务器获取 JSON 结果。

我需要有效地从返回的结果集中提取子集，一个对象数组。通过云到后端的多次调用是不行的。这一切都必须发生在客户端。

Flex ActionScript中是否有任何集合类可以通过对象都具有的共同属性之一对对象数组进行排序，例如Array sortOn方法，然后还提供二进制搜索方法可以从排序的对象中提取对象子集数组的版本，而不访问数组中的每个项目并进行比较？

例如，如果我有一个对象数组并且每个对象都有一个zip属性和一个name属性，我希望能够从原始数组的副本中提取所有zip = 10015 的对象，其中副本已排序拉链。

谢谢

我正在尝试优化一个在 JavaScript 中对字符串进行二进制搜索的函数。

二分搜索要求您知道键是==枢轴还是<枢轴。

但这需要在 JavaScript 中进行两次字符串比较，这与具有返回三个值（小于、等于、大于）C的函数的类似语言不同。strcmp()(-1, 0, +1)

JavaScript 中是否有这样的本机函数，它可以返回一个三元值，以便在二进制搜索的每次迭代中只需要一次比较？

来自维基百科：

排序列表实施：就像超市的收银台，但重要的人可以在不太重要的人面前“剪掉”。( O(n) 插入时间, O(1) 获取-下一次, O(n*log(n)) 构建)

我认为如果用二分查找算法搜索插入位置，插入时间复杂度应该是O(log(n))。这里我把作业的到达顺序作为一个优先因素。

那么我错了还是维基百科不正确？

更新：根据 TAOCP 对列表的严格定义：

线性列表是 n >=0 节点 X 1 , X[2], ... , X[n] 的序列，其基本结构属性仅涉及项目之间出现在一行中的相对位置。

我假设列表wikipedia 引用不是linked-list，它可能是array。

谢谢。

https://docs.oracle.com/javase/1.5.0/docs/api/java/util/Arrays.html

Sun 没有提到他们的二进制搜索实现的任何复杂性。这是一个错误吗？我知道应该是这样O(logn)，但是当他们没有明确说明这一点时，我会感到紧张。他们为他们的一些算法做，比如 Arrays.sort。

你们中的任何人都对实际实施有任何了解吗？我自己还没有机会下载源代码！我想这是一个微不足道的二分搜索，但 Sun 有时会调整算法以获得更好的性能。

我知道二叉搜索树上的按顺序遍历（访问左，访问根，访问右）给了我一个排序的结果。但是我需要在二叉树上进行后序遍历（访问左，访问右，访问根），结果应该给我排序的值。

为了实现这一点，我应该如何构建我的二叉树？

问题是扩展二分搜索算法，以最有效的方式在排序数组中查找目标值的所有出现。具体来说，该算法的输入是（1）整数的排序数组，其中一些数字可能出现多次，以及（2）要搜索的目标整数。算法的输出应该是一对索引值，指示数组中整数的第一次和最后一次出现（如果确实出现的话）。源代码可以是 c#、c、c++。

此外，我们可能需要查找索引的最大和最小比较次数是多少？

我查看了 BST 的一些代码，我可以看到每个节点都是一个结构。这是必要的吗？

在二分查找算法中，上界元素是array.length-1，那么如何找到数组的最后一个元素呢？

如果长度为 8 的数组元素的下限和上限分别为 6 和 7，那么我的中间元素输出为：

mid=(6+7)/2 即java中的6