问题标签 [binary-search]

我需要在不使用任何静态/全局变量的情况下找到二叉搜索树中的第 k 个最小元素。如何有效地实现它？我想到的解决方案是在 O(n) 中进行操作，这是最坏的情况，因为我打算对整个树进行中序遍历。但在内心深处，我觉得我没有在这里使用 BST 属性。我的假设解决方案是正确的还是有更好的解决方案？

尝试对 Book 对象的排序数组执行二进制搜索。

它不能很好地工作，它会为某些对象返回正确的结果，但不是全部。

我在纸上进行了循环，似乎由于向上四舍五入＃.5而错过了一个数字。

任何想法如何使这项工作？

我有以下代码行：

当我编译我的代码时，我收到以下错误：

我#include <algorithm>在文件的开头做了，我似乎无法找出错误。以下是函数调用中使用的容器：

谢谢。

For binary search, what is the average number of comparisons needed to find a record in a file?

对于一个项目，我需要实现二进制搜索。这种二分搜索允许重复。我必须获取与我的目标匹配的所有索引值。如果发现中间有重复，我考虑过这样做：

Target = G 假设有以下排序数组：

B、D、E、F、G、G、G、G、G、G、Q、RS、S、Z

我得到的是 7 的中间值。由于双方都有目标匹配，并且我需要所有目标匹配，我认为获取所有目标的一个好方法是检查 mid + 1 是否是相同的值。如果是，请继续向右移动，直到不是。所以，结果会是这样的：

B、D、E、F、G、G、G、G、G、G（中）、Q、RS、S、Z

然后我会从 0 到 mid 来计算目标匹配并将它们的索引存储到一个数组中并返回它。

如果中间是匹配的并且重复恰好在第一次在中间并且在阵列的两侧，这就是我正在考虑的方式。

现在，如果第一次不匹配怎么办？例如：

B、D、E、F、G、G、J、K、L、O、Q、R、S、S、Z

然后像往常一样，它会抓取中间，然后从 first 到 mid-1 调用二进制搜索。

B、D、E、F、G、G、J

由于 G 大于 F，调用从 mid+1 到 last 的二分查找。

G，G，J。

中场是一场比赛。既然是匹配，就从 mid+1 到 last 通过 for 循环搜索，并计算匹配的数量，并将匹配索引存储到数组中并返回。

这是二进制搜索获取所有重复项的好方法吗？如果您在我的算法中发现问题以及提示/建议（如果有），请告诉我。我看到的唯一问题是，如果所有匹配项都是我的目标，我基本上会搜索整个数组，但是如果是这样的话，我仍然需要获取所有重复项。

谢谢

顺便说一句，我的导师说我们不能使用向量、哈希或其他任何东西。他希望我们保持在阵列级别，并习惯于使用和操作它们。

我在这里有一个问题，但它没有保存。我无法平衡完全不平衡的树（右侧的节点 1-15）。

我遇到了麻烦，因为我得到了堆栈溢出。

它读取两个相等的字符串列表，并且应该打印出第一个列表中有多少单词也在第二个列表中找到，简单。没有给我expexted结果，我认为问题出在binary_search。你能告诉我为什么吗 ？

如何解决二叉搜索树中的重复问题？

我想制作一个通用的 BST，它可以由任何数据类型组成，但是如果我的 BST 是通用的，我不确定如何将内容添加到树中。我需要的所有代码都在下面。我希望我的 BST 由 Locations 组成，并按 x 变量排序。任何帮助表示赞赏。

主要感谢您的关注。

其他代码

使用二进制搜索在数组中定位所有 n 个已排序的不同整数所需的比较总数是多少？我认为数字是n log ₂ n（2 是底数），但我不确定。你怎么看？