Summary of Lineáris és bináris keresés

## Bevezetés a Keresési Algoritmusokba Az adatok kezelése és feldolgozása során az egyik leggyakoribb feladat egy adott elem megtalálása egy adathalmazban. Gondoljunk csak egy telefonkönyvre, ahol egy névhez tartozó telefonszámot keresünk, vagy egy online áruházra, ahol egy termékre szűrünk. Ezek a feladatok mind keresési algoritmusokat igényelnek. Két alapvető és széles körben használt keresési módszer a **lineáris (vagy szekvenciális) keresés** és a **bináris keresés**. Bár mindkettő ugyanazt a célt szolgálja, működési elvük és hatékonyságuk jelentősen eltér, különösen nagy adathalmazok esetén. Ebben az anyagban részletesen bemutatjuk mindkét algoritmust, összehasonlítjuk őket, és rávilágítunk a gyakori hibákra. ### Lineáris Keresés A lineáris keresés a legegyszerűbb keresési algoritmus. Működési elve rendkívül intuitív: az algoritmus sorban, az első elemtől kezdve végigmegy az adathalmaz minden egyes elemén, és összehasonlítja azt a keresett értékkel. Ha megtalálja az egyezést, visszaadja az elem pozícióját (indexét), és befejezi a keresést. Ha végigmegy az összes elemen anélkül, hogy megtalálná az értéket, akkor az érték nincs jelen az adathalmazban. > **Lineáris keresés definíciója:** Egy keresési algoritmus, amely az adathalmaz minden elemét sorban, az elejétől a végéig végigvizsgálja a keresett érték megtalálása céljából. **Működési elv és lépések:** 1. Kezdjük az adathalmaz első eleménél (index $0$). 2. Hasonlítsuk össze az aktuális elemet a keresett értékkel. 3. Ha az aktuális elem megegyezik a keresett értékkel, akkor az értéket megtaláltuk, és az algoritmus befejeződik. 4. Ha nem egyezik, lépjünk a következő elemre. 5. Ismételjük a 2-4. lépéseket, amíg az adathalmaz összes elemét meg nem vizsgáltuk, vagy amíg meg nem találtuk az értéket. 6. Ha az adathalmaz végére értünk anélkül, hogy megtaláltuk volna az értéket, akkor az nincs jelen az adathalmazban. **Példa lineáris keresésre:** Tegyük fel, hogy van egy számlistánk: $[12, 5, 28, 17, 3, 42]$, és a $17$-es számot keressük. * **1. lépés:** Összehasonlítjuk a $12$-t a $17$-tel. Nem egyezik. * **2. lépés:** Összehasonlítjuk az $5$-öt a $17$-tel. Nem egyezik. * **3. lépés:** Összehasonlítjuk a $28$-at a $17$-tel. Nem egyezik. * **4. lépés:** Összehasonlítjuk a $17$-et a $17$-tel. Egyezik! Az érték megtalálva a $3$. indexen (feltételezve, hogy az indexelés $0$-tól kezdődik). **Időkomplexitás (Hatékonyság):** A lineáris keresés időkomplexitása $O(n)$, ami azt jelenti, hogy a legrosszabb esetben (amikor az elem az adathalmaz végén van, vagy nincs is benne) az algoritmusnak az adathalmaz összes $n$ elemét meg kell vizsgálnia. Ez a lineáris arányosság azt jelenti, hogy ha az adathalmaz mérete megduplázódik, a kereséshez szükséges idő is megközelítőleg megduplázódik. Kis adathalmazok esetén ez elfogadható, de nagy adathalmazoknál rendkívül lassúvá válhat. **Mikor használjuk a lineáris keresést?** * Amikor az adathalmaz kicsi. * Amikor az adathalmaz nincs rendezve, és nem érdemes rendezni (például mert csak egyszer keresünk benne, vagy a rendezés költségesebb lenne, mint a lineáris keresés). * Amikor az adathalmaz egy láncolt lista, ahol a bináris keresés nem alkalmazható hatékonyan. ### Bináris Keresés A bináris keresés egy sokkal hatékonyabb keresési algoritmus, mint a lineáris keresés, de van egy nagyon fontos előfeltétele: **az adathalmaznak rendezettnek kell lennie**. Ez azt jelenti, hogy az elemeknek növekvő vagy csökkenő sorrendben kell állniuk. Ha az adathalmaz nincs rendezve, először rendezni kell, mielőtt bináris keresést alkalmaznánk. > **Bináris keresés definíciója:** Egy keresési algoritmus, amely rendezett adathalmazokban alkalmazható. A „felezd és uralkodj” elv alapján minden lépésben kizárja az adathalmaz felét, ahol a keresett érték biztosan nem lehet. **Működési elv és lépések:** A bináris keresés a „felezd és uralkodj” elven alapul. Ahelyett, hogy sorban haladna, az algoritmus minden lépésben kizárja az adathalmaz felét, ahol a keresett érték bizto