Re: Effiziente Suche in geordneter Liste

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

Hallo zusammen,

> Wenn man die Vorschrift
> aus dem "Sorting und Searching" von Gott Knuth direkt hinschreibt, dann
> sieht's genauso aus, wie das was Markus gepostet hat.

Die Unfehlbarkeit Knuths, die sich aus der ihm zugewiesenen Anrede
herleitet, vorausgesetzt, kann das nicht sein: Markus' posting

(* van Almsick *)
In[343]:= Clear[ ListRegulaFalsi]
ListRegulaFalsi[data_List, q_] :=
 FixedPoint[
  With[{middle = Ceiling[Mean[#]]},
    If[data[[middle]] < q, {middle, Last[#]}, {First[#],
      middle}]] &, {1, Length[data]}]

hat Fehler bei der Lokalisierung von Elementen am
Anfang bzw. vor dem Anfang der geordneten Liste:

In[349]:= ListRegulaFalsi[Range[10], #] & /@ {0, 1, 2, 3, 9, 10, 11}
Out[349]= {{1, 2}, {1, 2}, {1, 2}, {2, 3}, {8, 9}, {9, 10}, {10, 10}}

0, 1, 2, sind nicht zu unterscheiden im Output von ListRegulaFalsi,
dabei ist 0 nicht enthalten, 1 ist im ersten (punktförmigen) Intervall
und 2 im zweiten Intervall.

Der Solloutput ist:

{{1,1}, {1,1}, {1,2}, {2,3}, {8,9}, {9,10}, {10,10}}

weil das gelieferte Intervall nach unten offen und nach oben abgeschlossen  
ist.

Es fragt sich, ob man der regula falsi eine rekursive Implementation geben  
kann.

(* regula falsi rekursiv: fÃŒr streng monotone Listen *)
In[319]:= Clear[ ListRFR, checkPoint]

checkPoint[l_List, q_] := Which[q <= First[l], -1,
   First[l] < q <= Last[l], 0,
   Last[l] < q, 1] /; Length[l] > 0

ListRFR[l_List , q_, iImb_:-2] :=
  Block[{m = Ceiling[(1 + Length[l])/2],
    i0 = If[iImb == -2, checkPoint[l, q], iImb]},
   If[l[[m]] < q,
    m + ListRFR[Take[l, m - Length[l]], q, i0],
    ListRFR[Take[l, m], q, i0]
   ]
  ] /; Length[l] > 2

ListRFR[l_List, q_, iImb_:-2] :=
 Block[{i0 = If[iImb == -2, checkPoint[l, q], iImb], i1 = checkPoint[l,  
q]},
    Which[i0 == -1, {1, 1}, i0 == 0, If[i1 == -1, {0, 1}, {1, 2}],
    i0 == 1, {2, 2}]
 ] /; Length[l] == 2

ListRFR[l_List, q_, iImb_:-2] :=
 Block[{i0 = If[iImb == -2, checkPoint[l, q], iImb]},
   Which[i0 == -1, {1, 1}, i0 == 0, {0, 1}, i0 == 1, {1, 1}]
 ] /; Length[l] == 1

In[340]:= ListRFR[Range[10], #] & /@ {0, 1, 2, 3, 8, 9, 10, 11}
Out[340]= {{1,1}, {1,1}, {1,2}, {2,3}, {7,8}, {8,9}, {9,10}, {10,10}}

Die regula falso ist ersichtlich ungeeignet fÃŒr die rekursive Formulierung,
weil man bei den kÌrzesten Ìbrigbleibenden Listen FÀlle zu unterscheiden  
hat und
- was wichtiger ist - die Information ÃŒber die ursprÃŒngliche Lage des  
Elements
durch die Aufrufkette durchgeben muss.

Gruss
Udo.