Binary search on a real-valued answer
Binary search on a real-valued answer
When needed
Used when the desired answer is a real number, for example:
- length;
- time;
- probability;
- area.
Idea
For real numbers, you cannot correctly use the condition l < r, because numbers can be divided infinitely many times.
Therefore, one of two approaches is used:
- perform a fixed number of iterations;
- perform the search until the error becomes small enough.
Template
The number of iterations is chosen to ensure the required accuracy of the result (usually iterations are more than enough).