On 7/3/2009 10:05 AM kj apparently wrote:
> The context is the concept of a binary search. In one of their
> homeworks, my students will have two occasions to use a binary
> search. This seemed like a perfect opportunity to illustrate the
> idea of abstracting commonalities of code into a re-usable function.
> So I thought that I'd code a helper function, called _binary_search,
> that took five parameters: a lower limit, an upper limit, a
> one-parameter function, a target value, and a tolerance (epsilon).
> It returns the value of the parameter for which the value of the
> passed function is within the tolerance of the target value.
>
> This seemed straightforward enough, until I realized that, to be
> useful to my students in their homework, this _binary_search function
> had to handle the case in which the passed function was monotonically
> decreasing in the specified interval...
>
> The implementation is still very simple, but maybe not very clear,
> particularly to programming novices (docstring omitted):
>
> def _binary_search(lo, hi, func, target, epsilon):
> assert lo < hi
> assert epsilon > 0
> sense = cmp(func(hi), func(lo))
> if sense == 0:
> return None
> target_plus = sense * target + epsilon
> target_minus = sense * target - epsilon
> while True:
> param = (lo + hi) * 0.5
> value = sense * func(param)
> if value > target_plus:
> hi = param
> elif value < target_minus:
> lo = param
> else:
> return param
>
> if lo == hi:
> return None
1. Don't use assertions to test argument values!
2.
from scipy.optimize import bisect
def _binary_search(lo, hi, func, target, epsilon):
def f(x): return func(x) - target
return bisect(f, lo, high, xtol=epsilon)
3. If you don't want to use SciPy (why?), have them
implement http://en.wikipedia.org/wiki/Bisection_method#Pseudo-code
to produce their own `bisect` function.
hth,
Alan Isaac
--
http://mail.python.org/mailman/listinfo/python-list
