Re: Effiziente Suche in geordneter Liste

[Markus van Almsick <markusa@XXXXXXX.com>]

Hallo Martin,

hier ist eine einfache Implementation, die Log(n) Eigenschaften hat:

ListRegulaFalsi[data_List, q_] := 
 FixedPoint[
  With[
    {middle = Ceiling[Mean[#]]}, 
    If[data[[middle]] < q, {middle, Last[#]}, {First[#], middle}]
    ] &,
  {1, Length[data]}
  ]

Gruß, Markus 
Wolfram Research Inc.

On Jul 10, 2011, at 6:38 PM, Martin Heimann wrote:

> Liebe Kollegen,
> 
> vorgegeben ist eine streng monoton aufsteigende Liste {x(1), x(2), ... x(N)} reeller Zahlen. 
> 
> Wie finde ich am effizientesten die Indices ia und ib des Intervalls {x(ia},x{ib}} in welchem ein gegebener Wert y 
> liegt (d.h. x(ia)<y<=x(ib))? Simples sequentielles Suchen mit Position etc. benötigt Laufzeiten, welche proportional 
> der Anzahl Elemente der Liste sind. Es gibt jedoch Algorithmen, welche nur Laufzeiten proportional Log(N) benötigen; 
> in Mathematica habe ich jedoch nichts brauchbares gefunden. Habe ich hier etwas übersehen oder kennt jemand einen 
> bereits in Mathematica programmierten Algorithmus der derart effizient ist?
> 
> mit bestem Gruss
> Martin
> 
> ----------------------------------------------------------------------------
> Max-Planck-Institute for Biogeochemistry, PF 100164, D-07701 Jena, Germany 
> Street Address:  Beutenberg Campus, Hans-Knoell-Straße 10, D-07745 Jena
> Office:       +49-3641-57-6350/6301
> Mobile No:    +49-151-12035946
> Home:         +49-3641-618247                    
> Fax.:         +49-3641-57-7300
> Skype:   mheimann
> Email:   martin.heimann@XXXXXXX.de, 
>               office.bgc-systems@XXXXXXX.de
> Web:     http://www.bgc-jena.mpg.de/~martin.heimann
> 
> 
>