Lineáris keresés (algoritmus)

Teljes keresést (angolul linear search) használva találhatunk meg egy tetszőleges elemet egy nem rendezett tömbben. Amennyiben a tömb rendezett, érdemes a hatékonyabb Logaritmikus keresést használni.

A teljes keresés a legegyszerűbb keresés: a tömb elemeit sorra vesszük, amíg az adott elem nem egyenlő a kívánt elemmel.

Futásidő

A futásidő a tömb méretével lineárisan nő.

Pszeudó-kód

  Be: t tömb, n keresett szám 
  Ki: n szám t tömbben elfoglalt helye
  Program lin_ker
     x:=1
     Amíg t[x]<>n és x<hossz(t)
        x := x+1
     Ha t[x]=n
        Ki: x
     Egyébként
        Ki: nincs megoldás 
  Program vége

C++ programkód

   #include <iostream>
   using namespace std;
   int main() {
      int t[6] = {5, 6, 1, 9, -2, 0};
      int n = 9;
      int x = 0;
      while(x<6 && t[x] != n) {
         x++;
      }
      if(x<6) {
         cout<<"A keresett érték a tömb "<<x<<". eleme";
      } else {
         cout<<"A keresett érték nincs a tömbben.";
      }
      return 0;
   }

Lineáris keresés: Amennyiben a tömb rendezett, akkor a keresést korábban is befejezhetjük. Tegyük fel, hogy az elemek monoton nem csökkenő sorrendben állnak.

Pszeudó-kód

  Be: t tömb, monoton nem csökkenő sorrendben álló elemekkel, n keresett szám,
  Ki: n szám t tömbben elfoglalt helye
  Program lin_ker
     x:=1
     Amíg t[x]<n és x<hossz(t)
        x := x+1
     Ha x<hossz(t) és t[x]=n
        Ki: x
     Egyébként
        Ki: nincs megoldás 
  Program vége

Lásd még

Logaritmikus keresés