ternary search

TopCoder : EllysThreeRivers. SRM 543 DIV 2. 1000 points.


回答ヒントを読んで、termary searchという概念が出た。
ternary searchは、left, rightの間に単峰性(?)関数f(x)の最大値を探す。ただし、
  • for all a,b with A ≤ a < bx, we have f(a) < f(b), and
  • for all a,b with xa < b ≤ B, we have f(a) > f(b).
def ternarySearch(f, left, right, absolutePrecision): #left and right are the current bounds; the maximum is between them if (right - left) < absolutePrecision: return (left + right)/2 leftThird = (2*left + right)/3 rightThird = (left + 2*right)/3 if f(leftThird) < f(rightThird): return ternarySearch(f, leftThird, right, absolutePrecision) else: return ternarySearch(f, left, rightThird, absolutePrecision)
absolutePrecision : 定数。実数を扱う問題では、実数xに対して、x==0の比較演算子を使わず、代わりに、fabs(x) < absolutePrecisionを使う。同じ意味です。
  O                O                O                O
f(left)        f(leftThird)       f(rightThird)    f(right)

Ternary search は binary search と違う。