Ternary search (Editorial)

Let $f(x)$ be a continuous concave function that has a local minimum on the interval $[a;b]$. Ternary search can be used to find this point.

Choose g = a + (b - a) / 3, h = a + 2 \cdot (b - a) / 3. The points $g$ and $h$ divide the interval $[a;b]$ into three equal parts (hence the name “ternary search”). Compute the values $f(g)$ and $f(h)$.

• If f(g) \le f(h), then the minimum of $f$ lies in the interval $[a;h]$, so we set b = h.

• If f(g) > f(h), then the minimum lies in the interval $[g;b]$, so we set a = g.

The process continues until |a - b| > \epsilon.

Example

In this example, the function f(x) = x^2 - 2 \cdot x - 35 = (x - 7) (x + 5) is given. Its roots are x_1 = -5, x_2 = 7. The minimum of the function is attained at

The problem can also be solved using a known formula. The minimum of a quadratic function f(x) = ax^2 + bx + c~(a > 0) is attained at x = -b / (2a).

Therefore, for the function f(x) = x^2 + a \cdot x + b, the minimum is attained at x = - a / 2.

Algorithm implementation

Define the constant ɛ = 10^{-7}.

#define EPS 0.0000001

Define the function f whose minimum we want to find.

double f(double x)
{
  return x * x + a * x + b;
}

The function triple finds the minimum of $f(x)$ on the interval $[a;b]$.

double triple(double f(double x), double a, double b)
{
  double g, h;
  while (b - a > EPS)
  {
    g = a + (b - a) / 3;
    h = a + 2 * (b - a) / 3;
    if (f(g) <= f(h)) b = h; else a = g;
  }
  return (a + b) / 2;
}

The main part of the program. Read the input data. Run the ternary search. Find the point where the function $f(x)$ attains its minimum.

scanf("%lf %lf", &a, &b);
double x = triple(f, -100, 100);

Print the value of $x$.

printf("%.2lf\n", x);

Algorithm implementation -a/2

Read the input data.

scanf("%lf %lf", &a, &b);

Print the answer.

printf("%.2lf\n", -a/2);

Java implementation

import java.util.*;

public class Main
{
  static final double EPS = 0.0000001;
  static double a, b;

  static double f(double x)
  {
    return x * x + a * x + b;
  }

  static double triple(double a, double b)
  {
    double g, h;
    while (b - a > EPS)
    {
      g = a + (b - a) / 3;
      h = a + 2 * (b - a) / 3;
      if (f(g) <= f(h)) b = h; else a = g;
    }
    return (a + b) / 2;
  }
	
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    a = con.nextDouble();
    b = con.nextDouble();
    
    double x = triple(-100, 100);

    System.out.printf("%.2f\n",x);      
    con.close();
  }
}