Die Binäre eignet sich recht gut bei etwas größeren Datensätzen. Diese funktioniert nach dem Prinzip "Teile und Herrsche". Wir teilen, den kompletten Datensatz (sortiert) in 2 Teilen.

Ist das aktuelle Element größer als das gesuchte, vergleichen wir mit dem Element links vom Aktuellen. Ist das aktuelle Element kleiner, vergleichen wir mit dem Element rechts ob die unserem Suchergebnis entspricht. War die Suche erfolglos wird die Liste wieder in 2 Teilen aufgeteilt. Natürlich unter der Vorraussetung ob das Element der Mitte größer oder kleiner als das Gesuchte war. Im Schlechtesten Fall wird das erste oder das letzte Element gesucht.

Diese Art der Suche scheint optimal für reine Suchergebnisse. Sollten sie aber vor haben Elemente in den Datensatz einzufügen, wird das schnelle Suchergebnis schnell wieder dahin sein. Beim Einfügen eines neuen Elementes müssen sie wieder sorgen das die Liste sortiert bleibt.

Hierzu nun das Beispiel dazu welches voraussetzt das die Liste bereits sortiert ist. Algorithmen dazu finden sie den vorherigen Kapiteln.....

/*Download:binsear.c*/ #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX 255 struct plzn{ char ort[MAX]; unsigned int plz; }; struct plzn postleitzahlen[100]; static int N; /*Initialisieren*/ void init() { N = 0; postleitzahlen[N].plz = 0; strcpy(postleitzahlen[N].ort, "dummy"); } void einfuegen(unsigned int p, char o[]) { postleitzahlen[++N].plz = p; strcpy(postleitzahlen[N].ort, o); } int binaere_suche(unsigned int key) { int l=1; int r=N; int x; while(r>=l) { x=(l+r)/2; if(key < postleitzahlen[x].plz) /*kleiner?*/ r=x-1; /*die rechte Seite ist nicht mehr so interassant*/ else /*dann halt größer*/ l=x+1; /*die linke Seite ist nicht mehr so interessant*/ if(key == postleitzahlen[x].plz) /*Gefunden?*/ return x; } return -1; /*Nicht gefunden*/ } int main() { int wahl, ret; unsigned int search, post; char new_ort[MAX]; init(); do{ printf("-1- Postleitzahl suchen\n"); printf("-2- Postleitzahl hinzufügen\n"); printf("-3- Ende\n\n"); printf("Ihre Wahl : "); scanf("%d",&wahl); if(wahl == 1) { printf("Welche Postleitzahl suchen sie : "); scanf("%d",&search); ret=binaere_suche(search); if(ret == -1) printf("Kein Ergebnis auf Ihre Anfrage!\n"); else printf("Die Antwort auf %d : %s\n",search,postleitzahlen[ret].ort); } else if(wahl == 2) { printf("Neue Postleitzahl : "); scanf("%d",&post); printf("Ort für PLZ %d : ",post); scanf("%s",new_ort); einfuegen(post, new_ort); } }while(wahl!=3); return 0; }

Die Binäre Suche würde sich also prima für eine bereits kleinere sortierte Datenmenge eignen.