Searching in Mathematica

*To*: mathgroup at yoda.physics.unc.edu*Subject*: Searching in Mathematica*From*: Knut M|rken <knutm at ifi.uio.no>*Date*: Wed, 17 Mar 93 16:20:27 +0100

Given a list t of numbers, sorted in increasing order, and a number x, what is the best way to find an integer m such that t[[m]] <= x < t[[m]]? The obvious (?) way is to use the function Position as in Last[ Position[t, _?( # <= x& )] ] [[1]] and this works OK, but is slow if the list is long, since Position doesn't know that the list is sorted. I have written a binary search routine that does this much faster for long t, but somehow feel that searching in a sorted list is so fundamental that there ought to be a builtin function for this operation. Any comments? Knut Morken Dept. of Informatics University of Oslo Norway email: knutm at ifi.uio.no