Re: Effiziente Suche in geordneter Liste

["Udo und Susanne Krause" <su.krause@XXXXXXX.ch>]

Hallo Martin, Markus & Oliver,

> 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]}

In[92]:= Timing[ListRegulaFalsi[Range[10^8], 63725.3]]
Out[92]= {0.078, {63725, 63726}}

hier ist eine Funimplementation, die auch mit ungeordneten Listen  
funktioniert

In[88]:= Clear[heimannPosition]
heimannPosition[l_?VectorQ, q_?NumericQ] := {0, 1} +
   Plus @@ UnitStep[q - l];

In[93]:= Timing[heimannPosition[Range[10^8], 63725.3]]
Out[93]= {13.619, {63725, 63726}}

sehr langsam natürlich, aber kaum Code; und hier ist die Schönschrift
für die regula falsi, die somit auch kaum Code enthält:

In[121]:= Clear[ ListRF, m]
ListRF[data_List, q_] :=
 FixedPoint[
  Drop[{First[#], m = Ceiling[(Plus @@ #)/2], Last[#]},
    If[data[[m]] < q, 1, -1]] &, {1, Length[data]}]

In[123]:= Timing[ListRF[Range[10^8], 63725.3]]
Out[123]= {0.078, {63725, 63726}}

Gruss
Udo.