def BinarySearch(left, right, eps = 0.000001):
    steps_count = 0
    while right - left > eps:
        steps_count += 1
        m1 = left + (right - left) / 3.0
        m2 = right - (right - left) / 3.0
        if (f(m1) < f(m2)): 
            right = m2
        else:
            left = m1
    return (f((right+left) / 2.0), (right+left) / 2.0, steps_count)

def GoldenSection(left, right, eps = 0.000001):
     x = left + (right - left) * (3 - sqrt(5)) / 2.0
     y = left + right - x
     steps_count = 0
     while right - left > eps:
        steps_count += 1
        if f(x) < f(y):
            right = y
            y = x
            x = left + right - y
        else:
            left = x
            x = y
            y = left + right - x
     return (f((right+left) / 2.0), (right+left) / 2.0, steps_count)

def FibonachiSection(left, right, eps = 0.000001):
    def fib(n):
        if n < 3:
            return 1.
        return fib(n-1) + fib(n-2)
    steps_count = 0
    while right - left > eps:
       steps_count += 1
       x = left + fib(steps_count+2)/fib(steps_count+3) * (right - left)
       y = left + right - x
       if f(x) > f(y):
           right = y
       else:
           left = x
    return (f((right+left) / 2.0), (right+left) / 2.0, steps_count)