bsearch Funktion

[Peter (Gast)]

Hallo Leute,
eine kurze Frage:

Wieviele Vergleiche benötigt bsearch zum Sortieren von 100.000 
Elementen?
Vergleicht sie nicht das 1. Element mit den anderen 99.999,
dann das 2. mit den restlichen 99.998 und so weiter?

MfG

[Klaus W. (mfgkw)]

nein, bsearch macht binäre Suche (Intervallhalbierung nach jedem 
Vergleich).
Deshalb müssen ja die Daten auch sortiert sein.

Wer will das wissen? Hausuafgabe?

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Peter schrieb:
> Wieviele Vergleiche benötigt bsearch zum Sortieren von 100.000
> Elementen?

lb(n)

[Klaus W. (mfgkw)]

> lb(n)

aber nicht immer...

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Klaus W. schrieb:
>> lb(n)
>
> aber nicht immer...

Aber immer öfter ;-)

O(lb(n))

[Karl H. (kbuchegg)]

Peter schrieb:
> Hallo Leute,
> eine kurze Frage:
>
> Wieviele Vergleiche benötigt bsearch zum Sortieren von 100.000
> Elementen?
> Vergleicht sie nicht das 1. Element mit den anderen 99.999,
> dann das 2. mit den restlichen 99.998 und so weiter?

Dann wäre es aber eine bescheuerte Funktion.
In der Zeit als es noch gedruckte Telefonbücher gab, hat jeder das 
Verfahren des b_inary _search intuitiv angewendet.
Telefonbuch in der Mitte aufschlagen. Steht der gesuchte Name dort? 
Ja->gefunden. Nein? In welcher Hälfte muss er sein - vordere oder 
hintere Hälfte? Dort dann wieder in der Mitte aufschlagen etc. etc. 
Genau aus diesem Grund waren Telefonbücher nach dem Namen sortiert.

[Peter II (Gast)]

Karl H. schrieb:
> Dort dann wieder in der Mitte aufschlagen etc. etc.
> Genau aus diesem Grund waren Telefonbücher nach dem Namen sortiert.

wieso waren? Sind sie aktuell nach Rufnummer sortiert?

[PittyJ (Gast)]

Peter II schrieb:
> Karl H. schrieb:
>> Dort dann wieder in der Mitte aufschlagen etc. etc.
>> Genau aus diesem Grund waren Telefonbücher nach dem Namen sortiert.
>
> wieso waren? Sind sie aktuell nach Rufnummer sortiert?

Telefonbücher gibt es nicht mehr. Es werden keine mehr gedruckt.
Deshalb 'waren'.

[Mikro 7. (mikro77)]

Karl H. schrieb:

> In der Zeit als es noch gedruckte Telefonbücher gab, hat jeder das
> Verfahren des b_inary _search intuitiv angewendet.

OT: Naja, sagen wir mal so "ähnlich": Es gibt ja noch Buckets als 
Unterstützung (Anfangsbuchstabe) und die Intervallhalbierung läuft bei 
mir zumindest nicht so optimal. ;-)

Klaus W. schrieb:
>> lb(n)
>
> aber nicht immer...

Wann denn nicht?

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

S. J. schrieb:
> Wann denn nicht?

lb(n) ist doch nur die obere Grenze. Wenn Du den Eintrag vorher findest, 
dann werden entsprechend weniger Vergleiche nötig.

[Peter II (Gast)]

PittyJ schrieb:
> Telefonbücher gibt es nicht mehr.

http://www.telefonbuchversand.de/

das wissen scheinbar nicht alles und verkaufen es einfach noch.

[Mikro 7. (mikro77)]

Habe das so in Erinnerung, dass immer bis zum "Ende" gesucht werden muss 
(zwei nebeneinanderliegende Elemente). Der vewendete Operator ist ja "<" 
und nicht "==".

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

S. J. schrieb:
> Habe das so in Erinnerung, dass immer bis zum "Ende" gesucht werden muss
> (zwei nebeneinanderliegende Elemente). Der vewendete Operator ist ja "<"
> und nicht "==".

Ja, Du magst recht haben. Du halbierst den zu durchsuchenden Bereich mit 
jedem Schritt und prüft am Ende, ob Du das gesuchte Element gefunden 
hast. Da hat mich Klaus auf's flasche Gleis gelockt ;-)

[Nase (Gast)]

Hat eigentlich irgendjemand mal die Frage gelesen? SCNR

Peter schrieb:
> Wieviele Vergleiche benötigt bsearch zum Sortieren von 100.000
> Elementen?

[Klaus W. (mfgkw)]

Torsten R. schrieb:
> Ja, Du magst recht haben. Du halbierst den zu durchsuchenden Bereich mit
> jedem Schritt und prüft am Ende, ob Du das gesuchte Element gefunden
> hast. Da hat mich Klaus auf's flasche Gleis gelockt ;-)

Das ist ein harter Vorwurf...

Erstens gibt es Varianten von bsearch(), nicht alle sind exatk gleich.
MAn kann durchaus jeweils in der Intervallmitte auf GLeichheit testen.

Aber davon abgesehen ist die Länge auch nicht immer eine Zweierpotenz, 
und dann unterscheiden sich die Lauflängen zumindest um +/-1, je nachdem 
ob man in die kürzere oder die längere Hälfte verzweigt :-)
Also exakt gleich ist es nicht immer...

[Eric B. (beric)]

Nase schrieb:
> Hat eigentlich irgendjemand mal die Frage gelesen? SCNR
>
> Peter schrieb:
>> Wieviele Vergleiche benötigt bsearch zum Sortieren von 100.000
>> Elementen?

Dann heisst die Antwort also: unendlich viele, weil bsearch sortiert 
nicht ;-)

[Klaus W. (mfgkw)]

oh, du hast so recht...
Entweder meint er qsort oder suchen.