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: