Programozás‎ > ‎

Lineáris keresés

Feladat

Bemenet

Adott egy rendezetlen 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 K := E-től U-ig
    Ha a[K] = kulcs akkor "TALÁLAT(K)"
Ciklus vége
Ha nem volt "TALÁLAT" akkor "NEM TALÁLHATÓ"

Eljárás típusú megközelítés

K := az első lehetséges index
U := az utolsó lehetséges index
VOLT := hamis
Ciklus amíg K <= U és nem VOLT
    Ha a[K] = kulcs akkor
        VOLT := igaz
     különben
        K := K + 1
    Elágazás vége

Ciklus vége
Ha VOLT akkor "TALÁLAT(K)" különben "NEM TALÁLHATÓ" Elágazás vége
 

Hatékonyság

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

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 linearisKereses(int kulcs, int[] a) {
    for (int K = 0; K < a.length; K++) {
        if (a[K] == kulcs) return K;
    }
    return -1;
}