对于在排序数组中出现两次的键，如何计算二进制搜索的最坏情况时间？
使用二分搜索查找在排序数组中出现两次的键的最坏情况时间复杂度是多少？我知道对排序数组进行二分搜索的最坏情况时间复杂度是O（log n）。因此，在密钥出现多次的情况下，时间复杂度应小于O（log n）。但是，这个怎么算，我不太清楚。
共有1个答案
在最坏的情况下,二进制搜索需要执行log2（n）+1（/code）迭代来查找元素或得出元素不在数组中的结论。
例如，假设重复元素出现在数组的第一个索引和第二个索引中（如果它们在最后一个索引中，并且在最后一个索引之前，则相同）。在这种情况下,您将进行log2（n）比较,因此,仍然将O（log（n））作为最坏情况的时间复杂度。
-
由于splay树是一种不平衡的二元搜索树（brilliant.org/wiki/splay树），它不能保证最大高度为O（log（n））。因此，我认为它不能保证最坏情况下的搜索时间为O（log（n））。 但根据bigocheatsheet。通用域名格式： Splay树的最坏情况搜索时间为O（log（n））？？？
-
我想实现一种将排序数组插入二叉搜索树的算法，但我不希望最终得到一棵只向一侧生长的树。 你有什么想法吗？ 谢谢你。
-
我有一个二进制搜索树，它的每个节点都有两个值。 所以它的节点是这样的。 我已经根据节点的“name”变量的升序在BST中插入了值。所以树的顺序遍历将按“name”的升序返回节点。 现在我想根据“值”变量的升序显示树节点。无需更改原始树。哪种算法/方法对此最有效？
-
问题内容： 我在将这两种算法结合在一起时遇到麻烦。我被要求修改以返回将元素插入数组的索引。然后有人要求我实现一个使用my 对随机生成的数组进行排序的。 我按照预期的方式工作，每当我单独测试它时都返回正确的索引。我写信是为了了解它是如何工作的，并使其也能工作。一旦将两者结合在一起，它就会崩溃。我知道我在一起实施起来不正确，但是我不确定问题出在哪里。 这是我得到的： 我在运行它时得到的返回值是。有什么
-
我使用这个二进制搜索函数得到一个较大数据集的索引错误。当我输入一个较小的数据集时，即[1,2,3,4,5]搜索5。算法按预期运行。但是，当我获取下面的文本时，使用空参数列表（delimeter char为“”）调用string对象的split方法，并将字符串拆分为列表值，其中每个元素都是字符串，然后搜索单词“culpa”，我最终会出现以下错误： 索引错误：列表索引超出范围 非常感谢你的帮助。非常感
-
我可以使用什么样的算法将两个排序数组合并为一个排序数组，最坏情况下的时间复杂度为O（log（m n）），其中n，m是数组的长度？我对算法的经验很少，但我检查了merge-sort，似乎合并步骤的时间复杂度是O（n）。在O（log（n））中是否有不同的合并方法？ 编辑：我最初没有考虑过，但可能无法在O（log（n））中合并两个排序的数组？实际目标是找到两个排序数组的中值。有没有办法做到这一点而不合并