|
2.1 Das Sequentielle Suchen
Bei diesem Suchverfahren wird jedes Feld des Arrays nacheinander durchgelaufen, bis das entsprechende Feld gefunden ist. Im Durchschnitt benötigt man dafür N/2 Operationen.
Best Case: das Erste Feld entspricht der gesuchten Sozialversicherungsnummer.
Worst Case: Das n-te Feld entspricht der gesuchten Sozialversicherungsnummer.
Eine neues Feld wird am Ende des Arrays angefügt (n+1).
Für den hohen Durchschnitt der benötigten Operationen, die man bis zum Finden der gesuchten Sozialversicherungsnummer braucht (8 Mio Felder), ist das Sequentielles Suchen nicht gerade zweckführend. Eine andere Möglichkeit des Suchens ist
2.2 Das Binäre Suchen
Bei unserem zweiten Versuch ist ein sortiertes Array vorliegend, d.h. die Felder sind aufsteigend sortiert. Man nennt das auch ein sortiertes Array. Neue Felder werden am Ende der Liste angefügt, unabhängig davon, ob es sich um eine Neugeburt oder um einen Zuwanderer handelt. Siehe auch Kapitel Indexreorganisation.
Funktion: Beim Binären Suchen wird die Anzahl der Felder immer weiter halbiert. Dadurch gelangt man viel schneller zum gesuchten Feld gegenüber dem Sequentiellen Suchen, da sich die Menge der zu suchenen Felder systematisch verkleinert. Bei 8 Mio. Felder entspricht das 23 Suchschritten.
Frage: Wie oft kann man n Felder halbieren? -> ld n
2^x = 8 Mio
x = ld 8 Mio
x 23
Average Case entspricht ungefähr dem Worst Case beim Binären Suchen (=2^x).
2.2.1 Indexreorganisation
Beim Binären Suchen ist das Einfügen teurer als bei der Sequentiellen Sortierung, da die Reihenfolge erhalten werden muß.
Angenommen im Laufe eines Tages werden zu den 8 Mio. Feldern 30 neue hinzugefügt, so dauert die Suche der zuletzt angefügten Felder am Längsten. Das kommt daher, da zwar die ersten 8 Mio. Felder binär in 23 Schritten durchlaufen, die neu angefügten 30 Felder aber sequentiell im Worst Case bis zu 30 Mal zusätzlich abgeklappert werden.
Indexreorganisation wird meistens über Nacht oder zu Zeiten geringer Abfragen durchgeführt.
|
