Sort And Searching Question:

Download Questions PDF

As an example of the utility of binary search in scientific computing, we revisit a problem that we consider the problem of inverting an increasing function. To fix ideas, we refer to the Gaussian distribution Φ when describing the method. Given a value y, our task is to find a value x such that Φ(x) = y. In this situation, we use real numbers as the endpoints of our interval, not integers, but we use the same essential method as for guessing a hidden integer: we halve the size of the interval at each step, keeping x in the interval, until the interval is sufficiently small that we know the value of x to within a desired precision δ. We start with an interval (lo, hi) known to contain x and use the following recursive strategy:
☛ Compute m = lo + (hi - lo) / 2
☛ Base case: If (hi - lo) is less than δ, then return m as an estimate of x
☛ Recursive step: otherwise, test whether Φ(m) < y. If so look for x in (lo, m); if not look for x in (m, hi)
The key to this method is the idea that the function is increasing - for any values a and b, knowing that Φ(a) < &Phi(b) tells us that a < b, and vice versa. In this context, binary search is often called bisection search because we bisect the interval at each stage.