The mechanism of a binary search

To estimate the implied volatility, the logic underlying the earlier methods is to run the Black-Scholes-Merton option model a hundred times and choose the sigma value that achieves the smallest difference between the estimated option price and the observed price. Although the logic is easy to understand, such an approach is not efficient since we need to call the Black-Scholes-Merton option model a few hundred times. To estimate a few implied volatilities, such an approach would not pose any problems. However, under two scenarios, such an approach is problematic. First, if we need higher precision, such as sigma=0.25333, or we have to estimate several million implied volatilities, we need to optimize our approach. Let's look at a simple example.

Assume that we randomly pick up a value between one and 5,000. How many steps do we need to match this value if we sequentially run a loop from one to 5,000? A binomial search is the log(n) worst-case scenario...