A lineáris keresés tétele

Általános feladat: Rendelkezésre áll egy N elemű sorozat, egy, a sorozat elemein értelmezett T tulajdonság. Olyan algoritmust kell írni, amely eldönti, hogy van-e T tulajdonságú elem a sorozatban, és ha van, akkor megadja a sorszámát.

Algoritmus:

Eljárás

  I:=1

  Ciklus amíg I<=N és A(I) nem T tulajdonságú

    I:=I+1

  Ciklus vége

  HA I<=N akkor VAN          (A VAN egy logikai változó, ha van akkor true)

  Ha VAN akkor SORSZ:=I

  Ha I>N akkor NINCS

Eljárás vége.

Logaritmikus keresés

Általános feladat: Adott egy N elemű rendezett sorozat és egy keresett elem (X). Olyan algoritmust kell írni, amely eldönti, hogy szerepel-e a keresett elem a sorozatban, s ha igen, akkor megadja a sorszámát. Kihasználjuk, hogy a vizsgált sorozat rendezett. Ez alapján bármely elemről el tudjuk dönteni, hogy a keresett elem előtte vagy utána van-e, vagy esetleg éppen megtaláltuk. A és F mindig annak a részintervallumnak az alsó és felső végpontjai, amelyben a keresett elem benne lehet.

Algoritmus:

Eljárás

  A:=1 ; F:=N

  Ciklus

    K:=INT((A+F)/2)   (A és F által határolt intervallum középső elemére mutat rá)

    Ha A(K)<X akkor A:=K+1

    Ha A(K)>X akkor F:=K-1

  amíg A<=F és A(K)<>X

  Ciklus vége

  Ha A<=F akkor VAN

  Ha VAN akkor SORSZ:=K

Eljárás vége.