[Date Index] [Thread Index] [Author Index]

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