Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Finding Position in an ordered list

• To: mathgroup at smc.vnet.net
• Subject: [mg57770] Re: [mg57720] Finding Position in an ordered list
• From: János TÓTH <janostothmeister at gmail.com>
• Date: Wed, 8 Jun 2005 03:21:19 -0400 (EDT)
• References: <200506060821.EAA12541@smc.vnet.net> <76e8f81805060620315232bc54@mail.gmail.com>
• Reply-to: János TÓTH <janostothmeister at gmail.com>
• Sender: owner-wri-mathgroup at wolfram.com

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.

Janos

On 6/7/05, yehuda ben-shimol <bsyehuda at gmail.com> wrote:
> The immediate answer is to perform a binary search. This will result
> with a complexity of O(Log[2,n]) (n being the length of the list) and
> not O(n).
> There is an implementation of a binary search algorithm in the
> Combinatorica package
> << DiscreteMath`Combinatorica`
> ? BinarySearch
> 
> good luck
> yehuda
> On 6/6/05, janostothmeister at gmail.com <janostothmeister at gmail.com> wrote:
> > I wonder if it is possible to use the knowledge
> > that a list in which I am looking for the position
> > of an element is ordered. I want a quicker solution then e.g.
> > lis={ac,dmk,rfg,sty,zxxer}
> > Position[lis,sty]
> >
> > I am certainly interested in longer lists...
> >
> > Thank you,
> >
> > Janos
> >
> >
> >
>

• Follow-Ups:
  • Re: Re: Finding Position in an ordered list
    • From: Andrzej Kozlowski <andrzej@akikoz.net>

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