Let $[a,b]$ be some interval, and let $X \in [a,b] $ be some unknown number one would like to find (approximately). An example of this problem is finding the root of a real function which changes its sign exactly once on $[a,b]$. The bisection method then suggests we examine the two subintervals $[a,c],[c,b]$ with $c=(a+b)/2$, and see in which of these does $X$ lie. One then repeats this procedure until the length of the interval becomes as small as desired. Another way to put this is that one starts "walking" from $a$, using a step size of $\Delta x:=(a+b)/2$, and halves the step size every time the step goes beyond the root.
My question is, is this the fastest way to locate a number in an interval to arbitrary accuracy? What if one updates the step size according to $\Delta x \mapsto q \Delta x$ with $q \neq 1/2?$
Thank you!
Let take the extreme example :
Let say you want to find $X$ within an interval of distance $d$ and you take steps of size $d$, which mean you divide $[a,b]$ into $E({b-a\over d})+1$ sub intervals and scan through them.
Assuming $X$ is evenly distributed over $[a,b]$ then the expected number of steps before finding $X$ is half the number of sub-intervals ${E({b-a\over d})+1}\over 2$
Now with the bissecting method, first step you got an interval length of ${b-a\over 2}$, second step ${b-a\over 4}$ , ... , $n$-th step ${b-a\over 2^n}$. Remember you want to repeat until this interval length is less than $d$, so it will be satisfied at step $n_0$ with :
$$ n_0 = \min\left\{n :d \ge {b-a\over 2^n}\right\} = \min\left\{ n : n\log(2) \ge \log\left({b-a\over d}\right)\right\}$$
Now you can compare : for the first method, the estimated number of steps is proportional to $b-a\over d$ whereas with the bissecting method, you end up with a number of steps proportional to $\log\left(b-a\over d\right)$ which is better especially as $d$ decrease.