Re: Finding Position in an ordered list
- To: mathgroup at smc.vnet.net
- Subject: [mg57753] Re: [mg57720] Finding Position in an ordered list
- From: yehuda ben-shimol <bsyehuda at gmail.com>
- Date: Tue, 7 Jun 2005 02:04:07 -0400 (EDT)
- References: <200506060821.EAA12541@smc.vnet.net>
- Reply-to: yehuda ben-shimol <bsyehuda at gmail.com>
- Sender: owner-wri-mathgroup at wolfram.com
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
>
>
>
- References:
- Finding Position in an ordered list
- From: janostothmeister@gmail.com
- Finding Position in an ordered list