Lineáris keresés

Adott egy tömbünk, ami adatokat tárol. Ebből szükségünk van egy adott elem sorszámára, vagy tudnunk kell, hogy az adatok között megtalálható-e egy konkrét érték.

Erre a célra a legegyszerűbb algoritmus a lineáris keresés. Azért lineáris, mert a lelkét adó ciklus a tömb elejétől a végéig megnézi az elemeket, hogy egyeznek-e a keresett értékkel. Ha igen, akkor a keresett értékhez tartozó indexet eltároljuk egy változóban, a ciklust pedig megszakítjuk. Az eltárolt indexet pedig visszaadjuk a metódus végén.

A legjobb esetben a keresés azonnal végez, legrosszabb esetben viszont végig kell nézni az összes elemet, így az algoritmus futási ideje a tömb méretével lineárisan növekszik, vagyis a futási ideje lineáris. Az indexet tároló változó értékét célszerű az algoritmus elején -1 értékre választani, így ha nem található meg a keresett érték, akkor azt egyértelműen jelzi az index.

Egy lehetséges implementáció, ami -1-et ad vissza, ha a keresett elem nincs benne a tömbben:

using System;

namespace PeldaAlgoritmusLinkeres
{
    class Program
    {
        public static int Lineariskeres(int[] tomb, int elem)
        {
            int index = -1;
            for (int i = 0; i < tomb.Length; i++)
            {
                if (tomb[i] == elem)
                {
                    index = i;
                    break;
                }
            }
            return index;
        }

        static void Main(string[] args)
        {
            var tomb = new int[] { 9, 6, 0, 0, 1, 2, 2, 2, 3, 1, 5, 4, 8, 2, 8, 6 };

            int poz = Lineariskeres(tomb, 2);
            Console.WriteLine("A kettes indexe: {0}", poz);

            Console.ReadKey();

        }
    }
}

A program kimenete:

A kettes indexe: 5