Re: Finding Position in an ordered list

*To*: mathgroup at smc.vnet.net*Subject*: [mg57810] Re: Finding Position in an ordered list*From*: "Carl K. Woll" <carlw at u.washington.edu>*Date*: Thu, 9 Jun 2005 05:17:43 -0400 (EDT)*Organization*: University of Washington*References*: <200506060821.EAA12541@smc.vnet.net> <76e8f81805060620315232bc54@mail.gmail.com> <d868f9$bus$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

"János TÓTH" <janostothmeister at gmail.com> wrote in message news:d868f9$bus$1 at smc.vnet.net... > Dear All, > > 0. Now I disclose that I am looking for a word in a dictionary. > 1. Thank for the BinarySearch idea. It is much faster than Position. > 2. The idea of interpolation in the case of numbers is fantastic. > 3. However, I tried BinarySearch[{a,b,c},b] without being evaluated. > > Thus, I need further help. > > Thank for all of you. > [snip] Janos, Apparently the Combinatorica package BinarySearch function only accepts numeric keys. We can modify this function to work with any key as follows: binarysearch[d_, k_, ordf_:Less] := Module[{lo = 1, mid, hi = Length[d], c}, While[lo <= hi, If[(c = d[[mid = Quotient[lo + hi, 2]]]) === k, Return[mid]]; If[ordf[k, c], hi = mid - 1, lo = mid + 1]]; Return[lo - 1/2] ] Then, for your example, we would use the ordering function OrderedQ[{##}]&: binarysearch[{a, b, c}, b, OrderedQ[{##}] &] 2 Carl Woll

**References**:**Finding Position in an ordered list***From:*janostothmeister@gmail.com