问题标签 [ternary-search]

可能重复：
C 中的三元搜索

编写三级[ternary]搜索程序。

注意：三级搜索类似于二分搜索。在二分搜索中，我们考虑数组的两个部分，并选择一个部分作为下一个搜索空间。在三次搜索中，我们将数组分为 3 个相等的部分。为此，我们分别在数组的 1/3 和 2/3 处采用两个“中间”索引，middle1 和 middle2。然后我们选择三个部分之一并继续搜索。

另外，在最坏的情况下如何找到三元搜索的时间复杂度？

我的尝试：

如果要搜索的数字出现在（数组的）最后 2-3 个位置之一中，则它终止。我在哪里犯了错误？

三元搜索算法是一种快速算法，用于寻找单峰函数的最小值或最大值，该函数要么先增大后减小，要么先减小后增大。假设我们正在处理一个先减少然后增加的函数，并且我们想要找到最小值。三元搜索使用以下递归工作：

• 如果窗口的大小“足够小”，则返回它的中点。
• 除此以外：
  • 评估左右边界的函数；调用值 l 和 r。
  • 在 1/3 和 2/3 点评估函数；调用值 m ₁和 m ₂
  • 如果 m ₁ < m ₂，那么我们处于函数的递增区域，并且最小值不能在 m ₂和 r 之间。
  • 如果 m ₁ > m ₂，那么我们在函数的递减区域中，最小值不能在 l 和 m _1之间
  • 递归搜索未被丢弃的 2/3。

该算法运行迅速，因为它可以在每次迭代中不断抛出 1/3 的值。

然而，我觉得我错过了一些东西，因为我相信我们可以让这个算法运行得更快。特别要注意的是，我们总是丢弃边界和探测点之一之间范围的三分之一。这意味着我们保留了探测点和另一个边界之间的区域。因为三元搜索在 1/3 点处选择探测点，这意味着我们在每个点保留 2/3 的值。如果我们不是在 1/3 和 2/3 点处探测，而是在 1/2 - ε 和 1/2 + ε 点处探测一个极小的 ε 怎么办？这意味着我们将在每一步中丢弃 1/2 - ε 的范围，这意味着范围的大小将比我们每次仅丢弃 1/3 的元素时减小得快得多。

例如，如果我选择 ε = 1/1000，我们将在每次迭代中抛出 999/2000 的范围进行搜索。此处显示了经过一定次数的迭代后剩余的分数（三元搜索在左侧，我的算法在右侧：）

这个算法的修改版本是否比原始版本“更好”？或者我在这里遗漏了什么意味着我不应该使用修改后的策略来选择探测点？

我知道该函数执行了 ln(N)/ln(K) 次；但平均而言它会进行 K 次操作吗？

问题：

1. 是否有任何证据证明 k*ln(N)/ln(K) 是平均执行次数？
2. 如果这个公式是正确的，那么三元搜索将是最快的搜索，因为 k/ln(k) 将是最小值（对于整数），因为 3 是最接近“e”（实际最小值）的整数，这很容易证明使用差异化。

此外，我相信三元搜索更快；因为我制作了一个比较计算机程序。

下面有一个名为“test”的函数。我的程序无法通过测试功能。

这是我的三元搜索代码。三元搜索类似于二分搜索，但不是将所有元素除以二，而是将它们除以三。

为了使用三元搜索，我使用 index2 作为 1/3 项目的分隔符。index1 是 2/3 项的分隔符。

您只需将“高”和“低”分配给 index1 或 index2。这使您可以将列表分为三个部分。High 和 Low 用于查找您应该搜索的划分列表的哪一部分。然后这个过程不断重复，直到高和低的值彼此接近。

seq 是列表中的项目，即。[1,2,3,4,5...] 列表中的项目是按顺序排列的。

关键是我正在寻找的价值

并且 ternary_search 返回键的索引或接近键的数字的索引

玩得开心！干杯!

我试图解决 SPOJ 中的KOPC12A问题。

问题链接：http ://www.spoj.com/problems/KOPC12A/

问题简述：

给定 n 栋建筑物，每栋建筑物的高度（砖块的数量）都不同，每栋建筑物都有添加或移除砖块的成本，找到使所有建筑物具有相同高度的最小成本。

在尝试解决这个问题后，虽然徒劳无功，但在根据高度对输入进行排序后，我遇到了一个使用三元搜索的解决方案。

我无法理解平衡建筑物高度的成本是如何变成单峰的（因为三元搜索只能应用于单峰函数）

这让我很难过，我无法继续前进。

对此的任何见解都非常感谢。

谢谢-

我正在尝试解决这个问题：http ://acm.tju.edu.cn/toj/showp2886.html

我尝试了一些解决方案，我将解释其中的两个。请注意，两者都假设成本（位置）是一个凸函数，这意味着它向中间递减（实际上是向中间值（供应点）的某处），并且图表看起来或多或少像 U 形。

1. 找到cost(position) <= M的最左边和最右边的补给点位置。找到最小值和最大值后，我试着看看能不能把间隔弄大一点（因为餐厅不一定是地方正好在一个供应点上）。这是一个很好的解决方案，但需要非常多的时间来计算最后一位。它在 M 非常大且供应点很少且成本最低的测试中失败。复杂度：O(NlogN) + O(M)。下面的这个解决方案超出了时间限制，但我尝试了另一个解决方案，我在 O(1) 中计算我可以在两个方向上走多少，我得到了错误的答案。

2. 由于函数是凸函数，我可以使用三元搜索来找到最小值。如果最小值小于 M，则二分查找函数的下界和上界（即 M）。复杂性：O(NlogM)，因为对于每个 O(logM)，我都会计算 O(N) 中的成本。

这是我尝试过的，但我仍然得到“错误答案”，所以我需要一些帮助，因为这让我发疯。

这个问题在规格中并不是很清楚（或者至少我是这么认为的），因为当我第一次阅读它时，我不认为成本是从所有供应点计算的，而是从最近的供应点计算的。该示例清除了这一点。另外，我不知道我的成本（位置）函数是凸的假设是否真的正确。但是我尝试了很多例子，看起来确实如此。

谢谢。任何帮助表示赞赏。:D

就时间和空间复杂度而言，二分查找是否优于三元查找？

设A是一个由n 个正整数组成的数组。

我怎样才能找到A 的一些索引k使得：

有最小的绝对差（即abs(left - right)最小）？

由于这种差异的绝对函数是抛物线的（减少到最小差异然后增加，如U），我听说三元搜索用于在这样的函数中查找值（抛物线），但我不知道如何实现它，因为我在互联网上进行了搜索，但没有发现三元搜索在抛物线函数上的用途。

编辑：假设我的所有区间总和都在 O(1) 中，并且我需要比 O(n) 更快的东西，否则我不需要三元搜索..

假设我有知识库

如果我们问 prolog 是否

它会回答不，因为我们没有断言。除非我们明确说明，否则有什么方法可以使序言答案未知。

换句话说，我们是否可以要求 prolog 尽可能地对待未绑定的表达式而不是错误的。我一直在使用 IDP 系统，它允许存在量化并将未断言的关系视为不受约束而不是错误的，但我想使用更主流的东西。 http://adams.cs.kuleuven.be/idp/server.html

例如，在 IDP 中，您可以做出声明

哪个产量

我用 C 语言编写了一个程序，它将一个值和一个有序的整数数组作为输入，并执行三元搜索以在数组中找到值（如果存在）。

我已经在 Stackoverflow 中看到了使用 scanf 和相关主题的所有可能问题。

我注意到如果我以相反的顺序调用 2 个 scanf 函数，会有所不同。

如果我使用下面的代码。首先从用户那里读取值和数组之后，程序和 scanf 按预期运行。

尽管如果我以相反的顺序使用 scanf 输入，第二个 scanf 永远不会停止获取用户输入并读取缓冲区中剩余的值。

我不明白调用顺序有什么区别。我已经尝试过其他线程中提到的解决方案，但都没有奏效。

就像这里的参考是整个代码（按预期工作）：