Ugrás a tartalomhoz

linear search

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

linear search (tsz. linear searches)

  1. (informatika) lineáris keresés

A lineáris keresés egy egyszerű keresési algoritmus, amely egy adott elemet próbál megtalálni egy tömbben vagy listában. Az algoritmus sorban végignézi az elemeket, amíg meg nem találja a keresett értéket, vagy el nem éri a lista végét.

Hogyan működik a lineáris keresés?

  1. Elindulunk az adatszerkezet első elemétől.
  2. Sorban összehasonlítjuk az aktuális elemet a keresett értékkel.
  3. Ha találunk egyezést, visszaadjuk az elem indexét (pozícióját).
  4. Ha végigértünk az adatszerkezeten és nem találtuk meg a keresett elemet, akkor jelezzük, hogy nincs benne (például -1-et adunk vissza).

Lineáris keresés megvalósítása C++ nyelven

Az alábbi kód egy tömbben keres egy adott számot:

#include <iostream>

int linearisKereses(int tomb[], int meret, int keresett) {
    for (int i = 0; i < meret; i++) {
        if (tomb[i] == keresett) {
            return i; // Megtaláltuk az elemet, visszaadjuk az indexet
        }
    }
    return -1; // Ha nincs benne, -1-et adunk vissza
}

int main() {
    int tomb[] = {10, 20, 30, 40, 50};
    int meret = sizeof(tomb) / sizeof(tomb[0]);
    int keresett = 30;

    int index = linearisKereses(tomb, meret, keresett);
    
    if (index != -1) {
        std::cout << "Az elem megtalálható a(z) " << index << ". indexen.\n";
    } else {
        std::cout << "Az elem nincs a tömbben.\n";
    }

    return 0;
}

Lineáris keresés előnyei és hátrányai

Előnyök:

  • Egyszerű és könnyen érthető.
  • Nem igényel előrendezett adatokat.
  • Kisebb adatszerkezeteknél gyorsan megvalósítható.

Hátrányok:

  • Nagy tömböknél vagy listáknál lassú, mivel végig kell nézni az összes elemet a legrosszabb esetben.
  • Az időbeli bonyolultsága O(n), ami azt jelenti, hogy ha kétszer akkora a tömb, akkor a keresési idő is körülbelül kétszeresére nő.

Példa bemenet és kimenet

Bemenet:

tomb = {10, 20, 30, 40, 50}
keresett = 30

Kimenet:

Az elem megtalálható a(z) 2. indexen.

Hogyan lehet optimalizálni?

Ha az adatokat előrendezett formában tároljuk, hatékonyabb keresési algoritmusokat használhatunk, például bináris keresést (ami O(log n) sebességgel működik). Azonban a lineáris keresés még mindig hasznos kis méretű vagy rendezetlen adatszerkezeteknél.

Ez egy egyszerű, de alapvető algoritmus, amelyet érdemes ismerni, mert sok programozási probléma megoldásában hasznos lehet.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=linear_search&oldid=3502935”