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

http://en.wikipedia.org/wiki/Ternary_search

回答ヒントを読んで、termary searchという概念が出た。
ternary searchは、left, rightの間に単峰性(?)関数f(x)の最大値を探す。ただし、

• for all a,b with A ≤ a < b ≤ x, we have f(a) < f(b), and
• for all a,b with x ≤ a < 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 と違う。