geometrische Suche

[Mariexshhx]

Hallo, kennt sich jemand mit geometrischer Suche aus? Sie nutzt ja intern die binäre Suche. Ich suche eine Anforderung den die geometrische Suche an den Suchrraum hat, die aber die binäre Suche nicht hat.


Danke im vorraus 🙂

 

[MarvinsDepression]

Bist Du sicher, dass es 'geometrische Suche' heißen soll? Auf Wikipedia werde ich schon mal nicht fündig.
Ein 'Geometrisches Mittel' kenne ich dann aber schon. Das ist eine anderer Mittelwert im vergleich zum 'arithmetischen Mittel' und berechnet sich bei zwei Werten folgendermaßen: m = sqrt(a * b) und liefert im Allgemeinen kleinere Ergebnisse als m = (a + b) / 2.

 

[Mariexshhx]

Bist Du sicher, dass es 'geometrische Suche' heißen soll? Auf Wikipedia werde ich schon mal nicht fündig.
Ein 'Geometrisches Mittel' kenne ich dann aber schon. Das ist eine anderer Mittelwert im vergleich zum 'arithmetischen Mittel' und berechnet sich bei zwei Werten folgendermaßen: m = sqrt(a * b) und liefert im Allgemeinen kleinere Ergebnisse als m = (a + b) / 2.

Geometrische Suche - Enzyklopädie Marjorie-Wiki

marjorie-wiki.de

ich meine das leider findet man dazu sehr wenig

 

[KonradN]

Aber da gibt es keine zusätzlichen Anforderungen. Überall, wo Du die binäre Suche verwenden kannst, kannst Du auch diese geometrische Suche verwenden. Das macht aber nur dann Sinn, wenn man annimmt, dass der gesuchte Wert weiter vorne ist.

 

[MarvinsDepression]

Ah, OK. Das liest sich so, als dass man eben mit diesem Algorithmus das Suchinterval für die binäre Suche eingrenzt.
Läuft also vor der Binären Suche und übergibt dieser Ober- und Untergrenze des Intervalls im Array.

 

[Mariexshhx]

Aber da gibt es keine zusätzlichen Anforderungen. Überall, wo Du die binäre Suche verwenden kannst, kannst Du auch diese geometrische Suche verwenden. Das macht aber nur dann Sinn, wenn man annimmt, dass der gesuchte Wert weiter vorne ist.

Welche Bedingung muss für einen Suchraum gelten, dass dieser Suchalgorithmus
angewendet werden kann, aber nicht die binäre Suche aus der Vorlesung? So lautet genau die Fragestellung

 

[Mariexshhx]

Ah, OK. Das liest sich so, als dass man eben mit diesem Algorithmus das Suchinterval für die binäre Suche eingrenzt.
Läuft also vor der Binären Suche und übergibt dieser Ober- und Untergrenze des Intervalls im Array.

genau mir fällt aber einfach keine zusätzliche Anforderung ein die noch zusätzlich für diese vorherige Eingrenzung gelten muss.....

 

[KonradN]

Ich sehe da auch keine Anforderung. Die binäre Suche geht immer.

Man kann diskutieren, wann es Sinn macht - und das ist ja auch schon gegeben in dem Link: Wenn erwartet wird, dass der Treffer weit am Anfang steht, dann macht es Sinn. je weiter hinten der Eintrag ist, desto schlechter ist es.

 

[MarvinsDepression]

Stimmt, denn selbst in sehr großen Arrays mit hoher Trefferwahrscheinlichkeit weit vorne würde sich die binäre Suche sehr schnell diesem Bereich annähern. Da müssten schon sehr viele, solcher Array durchsucht werden, damit sich ein zusätzlicher vorgeschalteter Suchalgorithmus lohnt.