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

```

• Prev by Date: Re: goto and label (cont)
• Next by Date: Re: Output from Export[ ] (suggestion to Wolfram)
• Previous by thread: Re: Re: Finding Position in an ordered list
• Next by thread: Re: Finding Position in an ordered list