Square root (#3968)

Algorithm Analysis

Consider the function $f (x) = x^{2} + x$ . It is obvious that:

$f (0) = 0$ ;
$f (C) = C^{2} + C > C$ .

Thus, the root of the equation

f (x) = C

lies in the interval $[0; C]$ . The function $f (x)$ is strictly increasing. We search for the root $x$ using binary search.

Example

Consider the graph of the function $f (x) = x^{2} + x$ . It can be noticed that:

$f (0) = 0 < C$ ;
$f (C) = C + C > C$ .

Therefore, the root of the equation $f (x) = C$ lies in the interval $[0; C]$ and can be found by binary search.

Algorithm Implementation

Declare the constant EPS and the function f(x).

#define EPS 1e-10

double f(double x)
{
    return x * x + sqrt(x);
}

The main part of the program. Read the value of $C$ .

scanf("%lf", &c);

Set the binary search bounds [left; right] = [0; C].

left = 0; right = c;

Start the binary search.

while (right - left > EPS)
{
    middle = (left + right) / 2;
    y = f(middle);
    if (y > c) right = middle; else left = middle;
}

Output the answer.

printf("%lf\n", left);

Java Implementation

import java.util.*;

public class Main
{
    static double f(double x)
    {
        return x * x + Math.sqrt(x);
    }

    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        double c = con.nextDouble();
        double left = 0, right = c;

        while (right - left > 1e-10)
        {
            double middle = (left + right) / 2;
            double y = f(middle);
            if (y > c) right = middle; else left = middle;
        }
        System.out.println(left);
        con.close();
    }
}