még egyetlen napi bérlet sem, amikor nem kell keresnünk valamit a mindennapi életünkben, kocsikulcsot, könyvet, tollat, mobil töltőt és mit nem. Ugyanaz a számítógép élettartama, annyi adat van benne tárolva, hogy amikor a felhasználó valamilyen adatot kér, a számítógépnek meg kell keresnie a memóriájában, hogy megkeresse az adatokat, és elérhetővé tegye a felhasználó számára. A számítógépnek pedig megvannak a saját technikái a memória gyors keresésére, amelyekről többet megtudhat az operációs rendszer bemutató sorozatában.
mi van, ha programot kell írni egy adott szám kereséséhez egy tömbben? Hogy fogod csinálni?
Nos, egy adott tömb elemének kereséséhez két népszerű algoritmus áll rendelkezésre:
- lineáris keresés
- bináris keresés
lineáris keresés
a lineáris keresés nagyon egyszerű és egyszerű keresési algoritmus. A lineáris keresés során egy elemet vagy értéket keresünk egy adott tömbben úgy, hogy a tömböt a kezdetektől a kívánt elem vagy érték megtalálásáig bejárjuk.
összehasonlítja a keresendő elemet a tömb összes elemével, és ha az elem sikeresen illeszkedik, visszaadja a tömb elemének indexét, különben -1 értéket ad vissza.
lineáris keresést alkalmaznak rendezetlen vagy rendezetlen listákon, ha kevesebb elem van a listában.
a lineáris keresési algoritmus jellemzői
- az elemek rendezetlen és rendezetlen kis listájához használható.
- idő bonyolultsága O (n), ami azt jelenti, hogy az idő lineárisan függ az elemek számától, ami nem rossz, de nem is olyan jó.
- nagyon egyszerű megvalósítással rendelkezik.
a lineáris keresési algoritmust a következő oktatóanyagban valósítjuk meg.
bináris keresés
bináris keresés használt rendezett tömb vagy lista. A bináris keresés során a következő lépéseket követjük:
- kezdjük azzal, hogy összehasonlítjuk a keresendő elemet a lista/tömb közepén lévő elemmel.
- ha egyezést kapunk, visszaadjuk a középső elem indexét.
- ha nem kapunk egyezést, ellenőrizzük, hogy a keresendő elem értéke kisebb vagy nagyobb-e, mint a középső elem értéke.
- ha a keresendő elem/szám értéke nagyobb, mint a középső szám, akkor a középső elem jobb oldalán lévő elemeket választjuk ki(mivel a lista/tömb rendezve van, ezért a jobb oldalon az összes szám nagyobb lesz, mint a középső szám), és kezdjük újra az 1.lépéstől.
- ha a keresendő elem/szám értéke kisebb, mint a középső szám, akkor a középső elem bal oldalán lévő elemeket választjuk ki, és kezdjük újra az 1.lépéstől.
a bináris keresés akkor hasznos, ha egy tömbben nagyszámú elem van rendezve.
tehát a bináris keresés működéséhez szükséges feltétel a lista/tömb rendezése.
a bináris keresés jellemzői
- nagyszerű a nagy rendezett tömbök között keresni.
- az idő összetettsége O(log n), ami nagyon jó idő összetettség. Ezt részletesen a bináris keresési oktatóanyagban tárgyaljuk.
- egyszerű megvalósítással rendelkezik.