/*==============================================================
 * DURCHSUCHEN EINES NACH SCHLUESSEL SORTIERTEN ARRAYS
 * MIT HILFE DER BINÄREN SUCHE
 *============================================================*/

#include <stdio.h>
#include  "binsearch.h"

/*
 theKey: Zeiger auf den Schluesselwert des gesuchten
         Datensatzes.
 a : Zeiger auf den Beginn des Arrays.
 len : Anzahl der Array-Elemente
 
 */
void *binSearch(void           *theKey,
                my_array_t     *a,
                unsigned int   len ) {

    int ug, og, m;
    
    /* Initialisierung der Indices:
       Untergrenze auf Array-Anfang,
       Obergrenze auf Array-Ende,
       Mitte auf mittleren Index in ganzzahliger Division:
       Da die Unter- und Obergrenze sich während des Verlaufs
       ändern werden, nehmen wir sofort die allgemein
       gültige Formel:
 
           m = ug + (og - ug)/2 = (og + ug)/2
    */
    ug = 0;
    og = len - 1;
    m = (og + ug)/2;


    /* Suchschleife */
    while ( 0 != compareTo(a[m].key,theKey) && ug < og ) {

	/* Wenn der gesuchte Schluessel kleiner
           als a[m].k ist, suchen wir im Bereich
           ug..(m-1) weiter. Wenn größer, dann im Bereich
           (m+1)..og. */
        if ( compareTo(theKey,a[m].key) < 0 ) 
            og = m - 1;
        else
            ug = m + 1;

        /* der neue mittlere Index */
        m = (og + ug)/2;

    }

    /* Gefunden? */
    if ( compareTo(a[m].key,theKey) == 0 ) 
	return a[m].data;
    else
        return NULL;

}