设A 为n 个正整数的数组。
我怎样才能找到 A 的索引 k 这样:
left = A[0] + A[1] + ... + A[k]
right = A[k+1] + A[k+2] + ... + A[n]
具有最小绝对差值(即abs(left - right)最小)？
由于这个差异的绝对函数是抛物线的(减少到最小差异然后增加，像 U )，我听说三元搜索用于在这样的函数中查找值(抛物线)，但我不知道如何实现它，因为我在互联网上进行了搜索，但没有发现三元搜索在抛物线函数上的用途。
编辑:假设我的所有区间总和都在 O(1) 中，并且我需要比 O(n) 更快的东西，否则我不需要三元搜索..
最佳答案
让 left(k) 表示数组中从 A[0] 到 A[k] 的值的总和。证明是微不足道的:
left(k+1)=left(k)+A[k+1]
就是这样，如果您已经为给定的 k 计算了您的 left，那么 k+1 的 left > 通过将下一个元素添加到 left 来计算。
换句话说:
如果您遍历数组，从元素 #0 到元素 #n-1(其中 n 是数组的大小)，您可以计算 left< 的运行总计 只需将数组中的下一个元素添加到 left。
这似乎是显而易见且不言而喻的，但正式地说明这一点有助于流程的下一步变得同样显而易见。
同理，给定right(k)表示数组中从元素#k开始，直到数组最后一个元素的值之和，你也可以证明如下:
right(k+1)=right(k)-A[k]
因此，您可以找到 left(k) 和 right(k+1) 之间的差异最小的 k (I' m 使用与你的问题使用的符号略有不同，因为我的符号更方便)从数组中所有值的总和开始作为 right(0) 和 A[0] 为left(0)，然后计算right(1)，然后，从头开始迭代数组到尾，计算两个left 和 right 在每个步骤中，即时计算左右值之间的差异。找到差异最小的地方变得微不足道。
我想不出任何其他方式来做到这一点，不到 O(n):
1) 计算数组中所有值的总和，因为right(0)的初始值为O(n)。
2) 右边的迭代当然是 O(n)。
我不相信对数二分查找在这里起作用，因为值 abs(left(k)-right(k)) 本身不会按排序顺序排列。
顺便说一句，使用这种方法，当数组也包含负值时，您也可以找到最小差值。唯一的区别是，由于差异不再是抛物线，您只需遍历整个数组，只需跟踪 abs(left-right) 最小的位置即可。
关于c++ - 三元搜索以在数组中找到差异最小的点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37911533/