4. fejezet - Keresések

A keresés alapfeladata: egy adott struktúrában keressünk meg egy bemenetként megadott jellemzőjű elemet. Az egyszerű kereséseknél nem követelünk meg különösebb összefüggést a struktúra elemei között, míg a speciális kereséseknél ezt megtehetjük. A fejezetben csak olyan algoritmusokat tárgyalunk, amelyek már egyszerűbb - tömb, illetve lista - adathalmazokon is értlmezhetők. Az összetettebb adatstruktúrákon, mint például a keresőfákon működő algoritmusokról később ejtünk szót.

A kereső feladatok alapvetően két csoportra bonthatók: 1. egy konkrét elem 2. egy speciális tulajdonságú elem megkeresése az adott struktúrában.

Az előbbire példa, hogy egy egészeket tartalmazó tömbben keressük meg, a 15 előfordulását, míg az utóbbira, hogy az előbb említett tömbben keressük meg a legkisebb elemet.

4.1. Külső elem keresése

Az alapstruktúra legyen egy számokból álló egyszerű tömb. A feladat keressük meg a T tömbben az a elem első előfordulásának helyét. Ha nincs benne a tömbben, a visszatérési érték legyen a tömb mérete. Amennyiben nem követeljük meg az első előfordulást, a végeredmény nem egyértelmű.

Procedure Keres(T,a) 
Input: A T tömb és a keresendő a
Eredmény: A legkisebb i, amelyikre T[i]=a, vagy T.hossz, ha nincs ilyen 
1 i = 0 
2 while (i≤T.hossz) and (T[i]!=a) do 
3    i++
4 endw
5 Return(i)

Az algoritmus legrosszabb esetben a bemenő tömb minden elemével összehasonlítja a keresendő elemet. Időbonyolultsága ez alapján T.hossz, vagyis az algoritmus lineáris futásidejű.