Array-> Suchalgorithmuns

[Ich (Gast)]

Hallo Leute,

folgendes Problem kann ich nicht um setzen.

Gegeben:
Ein Array mit 1000 Einträgen. Die Werte im Array sind alle aufsteigend.
Der kleinste Wert im kleinsten Index der groesste Wert im groessten 
Index.

u_16 Array[1000]
{
....
 101, 102, 103, 104, 105, 106, 107,
 108, 109, 110, 111, 112, 113, 114,
...usw
}

Jetzt ist eine Zahl bekannt z.B. 113.
Wie ermittele ich am einfachsten welcher Index dem Wert 113 zugeordnet 
ist?

I = 0;
while ((Array[I] < 113) && (I < 1000))
{
 I++;
}

Bei dieser Lösung wird das ganze Array durchgeorgelt.
Geht es nicht auch irgendwie einfacher?

[Klaus R. (klara)]

Ich schrieb:
> Geht es nicht auch irgendwie einfacher?

Einfacher nicht, aber schneller. Such mal nach "binäre Suche".
Gruss Klaus.

[Max H. (hartl192)]

Du könntest schauen ob Array[500] < 113, mit dieser Info musst du dann 
nur mehr halbe Array durchsuchen.
Oder wenn Array[500] < 113 ist, dann schauen ob Array[25] < 113 ist…

[greg (Gast)]

In der C-Standardlibrary ist binäre Suche bereits implementiert, mit der 
Funktion "bsearch".

[Ich (Gast)]

Binaere Suche war das Stichwort.
Danke.

So gehts:

int binary_search(const int M[], const int eintraege, const int suchwert)
{
    const int NICHT_GEFUNDEN = -1 ;
    int mitte;
    int links = 0;                      /* man beginne beim kleinsten Index */
    int rechts = eintraege - 1;         /* Arrays-Index beginnt bei 0 */
 
    /* Solange die zu durchsuchende Menge nicht leer ist */
    while (links <= rechts)   
    {
        mitte = links + ((rechts - links) / 2); /* Bereich halbieren */
 
        if (M[mitte] == suchwert)       /* Element suchwert gefunden? */
            return mitte;
        else
            if (M[mitte] > suchwert)
                rechts = mitte - 1;     /* im linken Abschnitt weitersuchen */
            else /* (M[mitte] < suchwert) */
                links = mitte + 1;      /* im rechten Abschnitt weitersuchen */
            /* end if */
        /* end if */
    }
 
    return NICHT_GEFUNDEN;
}