Module: Binary search for a monotonic function


Problem

1/5

Binary search for a monotonic function

Theory Click to read/hide

Binary search can be used not only to find elements in an array, but also to find the roots of equations and the values ​​of monotonic (increasing or decreasing) functions.

Let us be given a monotonic function f and some value C of this function. Find the value of the x argument of this function, such that \(f(x)=C\).
 
Example of an increasing monotonic function:


We choose such boundaries where the value of the function is exactly greater and exactly less than the given value. Let's choose the value in the middle of this segment. If it is less than the given one, then we shift the left border to the middle of the segment. Otherwise, we will shift the right border. Next, we repeat the process of narrowing the boundaries. But there is a problem is that when to stop searching. Read more here.
 
For example, consider the problem of finding the square root of the number x. The square root of x (denoted by \(\sqrt x\)) is a number y such that < span class="math-tex">\(y^2 = x\).
Let's formulate the problem as follows: for a given real number x (\(x >= 1\)) find the square root with an accuracy not less than 5 characters after the dot.
 


Selecting the border of the segment for searching

Since we can't check for the whole infinity of numbers, we need to define the boundaries of the search for the root. First, let's find the left border, select an arbitrary negative point (for example: -1). We will double it until the value in it is greater than the given value. In order to find the right border, we choose an arbitrary positive point (for example: 1). We will double it until the value of the function at this point is less than the specified one.


Or, if we know exactly the boundaries of the search, we can take 1 as the left boundary, and the number itself x.
After that, we divide the current segment in half, square the middle, and if it is greater than x, then replace the upper face, otherwise  bottom.
 
Final implementation:

where,
eps - the accuracy to which the solution must be sought,
x - given number whose square root we are looking for,
m - the number in which the result will be stored after the algorithm is executed.
 

Problem

Given a natural number x. Calculate the cube root of a number.
 
Input
Number x – natural, not exceeding \(10^6\).
 
Output
The program should display a single number: the answer to the problem with an accuracy of at least 6 decimal places.

 

Examples
# Input Output
1 2 1.259921

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <iostream>
using namespace std;

double Search_Binary(int x)
{         
	
}

int main()
{
	
	int x;
	cin >> x;
	
	double res = Search_Binary(x);
	printf("%.8lf", res);


}

     

Program check result

To check the solution of the problem, you need to register or log in!