Programozás‎ > ‎

Bináris keresés

Feladat

Bemenet

Adott egy rendezett a[ ] tömb és egy kulcs, amit keresünk.

Kimenet

A kulcs tömbbeli indexe, vagy annak jelzése, hogy nem található a keresett kulcs.

Algoritmusok 

Függvény típusú megközelítés

E := az első lehetséges index
U := az utolsó lehetséges index
Ciklus amíg E <= U
    K := (E+U) / 2
    Ha kulcs < a[K] akkor U := K - 1
    különben Ha kulcs > a[K] akkor E := K + 1
    különben "TALÁLAT(K)"
Ciklus vége
Ha nem volt "TALÁLAT" akkor "NEM TALÁLHATÓ"

Hatékonyság

Egy véletlenszerűen kiválasztott - a tömbben megtalálható - kulcs keresése legrosszabb esetben  log2N lépést igényel, ha N a tömb hossza. A sikertelen keresések lépésszáma log2N.

Kódok

Java

Mivel Java-ban 0-tól kezdődik a tömbök indexelése, a -1 használható annak jelzésére, hogy nem volt találat.

int binarisKereses(int kulcs, int[] a) {
    int E = 0;
    int U = a.length - 1;
    while (E <= U) {
        int K = E + (U - E) / 2;
        if (kulcs < a[K]) U = K - 1;
        else if (kulcs > a[K]) E = K + 1;
        else return K;
    }
    return -1;
}