4 ms·
"On a different philosophical note, the real number line is nothing but a sorted array, and every equation solving problem is thus analogous to a search problem
by greenyoda 9y ago
"On a different philosophical note, the real number line is nothing but a sorted array, and every equation solving problem is thus analogous to a search problem. Since binary search happens to be an excellent search algorithm, we can use it for all such problems."
The example in this article isn't about searching the real number line - it's about searching for the solution to some real-valued function, whose values aren't guaranteed to be "sorted" (think of sin(x), or sin(1000x)).
There are functions for which this algorithm may not work - I'm guessing that the algorithm requires the function to be continuous, and possibly differentiable. For example, what happens if the function goes to infinity in the middle of the search range, like f(x) = 1/x between -1 and 1? And what if it has no real solutions at all, like x^2 + 1 = 0?
The algorithm also assumes that it would be possible to guess the range of x values that bound the solution (e.g., low = 1, high = 1000). What if the solution happens to be x = -10000000? This points to a big difference between the finite arrays that binary search works on, and the infinite domains and ranges of real-valued functions.