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

#include <stdio.h>


/************************************************************** 
 * der zu  durchsuchende Array 
 **************************************************************/

#define ARRAY_LEN 7

typedef struct {
    int key; /* Schluessel */
    char name[10]; /* Daten, 1.Feld */
    int  gehalt; /* Daten, 2. Feld */
} my_array_t;


/* Fuer das Beispiel wird der Array konstand belegt */
my_array_t a[ARRAY_LEN] =
{ { 1, "Mueller", 2400 },
  {2, "Zorn", 2800 },
  {7, "Fritz", 1400 },
  {22, "Freund", 2200 },
  {27, "Zahlten", 2100 },
  {28, "Baggins", 2111 },
  {33, "Harald", 2444 },
};




int main() {

    int theKey;
    int ug, og, m; /* Indices fuer Untergrenze/Obergrenze/Mitte */

    /* gesuchten Schluessel einlesen */
    printf("Schluessel : ");
    scanf("%d",&theKey);
    printf("Start der Suche ... ");
    
    /* 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 = ARRAY_LEN - 1;
    m = (og + ug)/2;


    /* Suchschleife */
    while ( 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 ( theKey < a[m].key ) 
            og = m - 1;
        else
            ug = m + 1;

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

    }

    /* Gefunden? */
    if ( a[m].key == theKey ) 
	printf("gefunden:\n Schluessel %d Name %s Gehalt %d\n",
	       a[m].key,a[m].name,a[m].gehalt);
    else
        printf("Schluessel nicht gefunden.\n"); 

}