Array-> Suchalgorithmuns

Ich Gast #3485766
Lesenswert?
• ▲
▼ 
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?
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Ich Gast #3485788
Lesenswert?
• ▲
▼ 
Binaere Suche war das Stichwort.
Danke.

So gehts:
1
int binary_search(const int M[], const int eintraege, const int suchwert)

2
{

3
    const int NICHT_GEFUNDEN = -1 ;

4
    int mitte;

5
    int links = 0;                      /* man beginne beim kleinsten Index */

6
    int rechts = eintraege - 1;         /* Arrays-Index beginnt bei 0 */

7
 

8
    /* Solange die zu durchsuchende Menge nicht leer ist */

9
    while (links <= rechts)   

10
    {

11
        mitte = links + ((rechts - links) / 2); /* Bereich halbieren */

12
 

13
        if (M[mitte] == suchwert)       /* Element suchwert gefunden? */

14
            return mitte;

15
        else

16
            if (M[mitte] > suchwert)

17
                rechts = mitte - 1;     /* im linken Abschnitt weitersuchen */

18
            else /* (M[mitte] < suchwert) */

19
                links = mitte + 1;      /* im rechten Abschnitt weitersuchen */

20
            /* end if */

21
        /* end if */

22
    }

23
 

24
    return NICHT_GEFUNDEN;

25
}
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren