Mielőtt megértenénk a lineáris és a bináris keresés közötti különbségeket, először külön kell ismernünk a lineáris és a bináris keresést.
Mi az a lineáris keresés?
A lineáris keresést szekvenciális keresésnek is nevezik, amely egyszerűen minden elemet egyszerre pásztáz. Tegyük fel, hogy egy tömbben vagy listában egy elemet akarunk keresni; egyszerűen kiszámítjuk a hosszát, és nem ugrunk egyetlen elemre sem.
Nézzünk egy egyszerű példát.
Tegyük fel, hogy van egy 10 elemből álló tömbünk, ahogy az alábbi ábrán látható:
A fenti ábra egy 10 értékű karaktertípust mutat be. Ha 'E'-re akarunk keresni, akkor a keresés a 0-tól kezdődikthelemet, és addig vizsgálja az egyes elemeket, amíg az elemet, azaz az „E” nem találja. Nem tudunk közvetlenül ugrani a 0-rólthelem a 4-hezthelemet, azaz minden elemet egyenként vizsgálunk, amíg az elemet nem találjuk.
A lineáris keresés összetettsége
A lineáris keresés során az egyes elemeket egyenként vizsgálja, amíg az elemet nem találja. Ha az elemek száma nő, akkor a vizsgálandó elemek száma is megnövekszik. Elmondhatjuk, hogy a Az elemek kereséséhez szükséges idő arányos az elemek számával . Ezért a legrosszabb eset bonyolultsága O(n)
Mi az a bináris keresés?
A bináris keresés olyan keresés, amelyben a középső elem kiszámítása annak ellenőrzésére történik, hogy kisebb vagy nagyobb-e, mint a keresendő elem. A bináris keresés használatának fő előnye, hogy nem vizsgálja meg a lista minden elemét. Az egyes elemek beolvasása helyett a lista feléig hajtja végre a keresést. Tehát a bináris keresés kevesebb időt vesz igénybe egy elem keresése, mint a lineáris keresés.
Az egyik bináris keresés előfeltétele az, hogy egy tömbnek rendezett sorrendben kell lennie, míg a lineáris keresés rendezett és rendezetlen tömbön is működik. A bináris keresési algoritmus az oszd meg és uralkodj technikán alapul, ami azt jelenti, hogy rekurzív módon osztja fel a tömböt.
A bináris keresésben három esetet használnak:
1. eset: adatok
2. eset: data>a[mid], then right=mid-1
3. eset: data = a[mid] // elem található
A fenti esetben ' a ' a tömb neve, középső az elem rekurzívan számított indexe, adat a keresendő elem, bal jelöli a tömb bal oldali elemét és jobb azt az elemet jelöli, amely a tömb jobb oldalán található.
Ismerjük meg a bináris keresés működését egy példán keresztül.
Tegyük fel, hogy van egy 10 méretű tömbünk, amely 0-tól 9-ig van indexelve, ahogy az alábbi ábrán látható:
70 elemet szeretnénk keresni a fenti tömbből.
1. lépés: Először kiszámoljuk egy tömb középső elemét. Két változót veszünk figyelembe, azaz a bal és a jobb oldalt. Kezdetben bal = 0 és jobb = 9, ahogy az alábbi ábrán látható:
A középső elem értéke a következőképpen számítható ki:
Ezért mid = 4 és a[mid] = 50. A keresendő elem 70, tehát a[mid] nem egyenlő az adatokkal. A 2. eset teljesül, azaz data>a[mid].
2. lépés: Mivel adat>a[közép], így a bal értéke mid+1-gyel növekszik, azaz bal=közepe+1. A mid értéke 4, így a bal értéke 5 lesz. Most kaptunk egy altömböt az alábbi ábrán látható módon:
Most ismét a középértéket a fenti képlet segítségével számítjuk ki, és a mid értéke 7 lesz. Most a középértéket a következőképpen ábrázolhatjuk:
A fenti ábrán azt figyelhetjük meg, hogy a[mid]>adat, tehát ismét a mid értéke kerül kiszámításra a következő lépésben.
3. lépés: A[közép]>adatként a jog értéke 1 közepére csökken. A mid értéke 7, így a jobb értéke 6 lesz. A tömb a következőképpen ábrázolható:
A mid értéke ismét kiszámításra kerül. A bal és a jobb értéke 5, illetve 6. Ezért a mid értéke 5. Most a mid egy tömbben ábrázolható az alábbiak szerint:
A fenti ábrán megfigyelhetjük, hogy a[mid]
4. lépés: mint [közép] Most ismét kiszámítjuk a mid értékét a már tárgyalt képlet segítségével. A bal és a jobb értéke 6, illetve 6, így a mid értéke 6 lesz, ahogy az alábbi ábrán látható: A fenti ábrán megfigyelhetjük, hogy a[mid]=adat. Ezért a keresés befejeződött, és az elem sikeresen megtalálható. A lineáris keresés és a bináris keresés közötti különbségek a következők: Leírás A lineáris keresés olyan keresés, amely úgy talál egy elemet a listában, hogy egymás után keresi az elemet, amíg az elemet meg nem találjuk a listában. Másrészt a bináris keresés olyan keresés, amely rekurzív módon megkeresi a lista középső elemét, amíg a középső elemet nem egyeztetjük a keresett elemmel. Mindkét keresés működik A lineáris keresés az első elemtől kezdi a keresést, és egyszerre egy elemet pásztáz anélkül, hogy a következő elemre ugorna. Másrészt a bináris keresés a tömb középső elemének kiszámításával a tömböt felére osztja. Végrehajtás A lineáris keresés bármilyen lineáris adatstruktúrán megvalósítható, mint például vektor, egyszeresen linkelt lista, dupla linkelt lista. Ezzel szemben a bináris keresés megvalósítható azokon az adatstruktúrákon, amelyeken kétirányú bejárás van, azaz előre és hátra. Bonyolultság A lineáris keresés könnyen használható, vagy mondhatjuk, hogy kevésbé bonyolult, mivel a lineáris kereséshez az elemeket tetszőleges sorrendbe lehet rendezni, míg a bináris keresésnél az elemeket meghatározott sorrendbe kell rendezni. Rendezett elemek A lineáris keresés elemei véletlenszerű sorrendbe rendezhetők. A lineáris keresésnél nem kötelező, hogy az elemek rendezési sorrendbe legyenek rendezve. Másrészt a bináris keresésnél az elemeket rendezett sorrendbe kell rendezni. Növekvő vagy csökkenő sorrendbe rendezhető, ennek megfelelően módosul az algoritmus. Mivel a bináris keresés rendezett tömböt használ, az elemet a megfelelő helyre kell beilleszteni. Ezzel szemben a lineáris kereséshez nincs szükség rendezett tömbre, így az új elem könnyen beilleszthető a tömb végére. Megközelítés A lineáris keresés iteratív megközelítést használ az elem megtalálásához, ezért szekvenciális megközelítésként is ismert. Ezzel szemben a bináris keresés a tömb középső elemét számítja ki, tehát az oszd meg és uralkodj megközelítést alkalmazza. Adatkészlet A lineáris keresés nem alkalmas nagy adathalmazhoz. Ha azt az elemet akarjuk keresni, amely a tömb utolsó eleme, akkor a lineáris keresés az első elemtől kezdi a keresést, és az utolsó elemig tart, így az elem keresése sok időt vesz igénybe. Másrészt a bináris keresés alkalmas nagy adathalmazhoz, mivel kevesebb időt vesz igénybe. Sebesség Ha az adathalmaz nagy a lineáris keresésben, akkor a számítási költség magas lenne, és a sebesség lelassulna. Ha az adathalmaz nagy a bináris keresésben, akkor a számítási költség kisebb lenne a lineáris kereséshez képest, és a sebesség gyors lesz. Méretek A lineáris keresés egy- és többdimenziós tömbön is használható, míg a bináris keresés csak az egydimenziós tömbön valósítható meg. Hatékonyság A lineáris keresés kevésbé hatékony, ha figyelembe vesszük a nagy adathalmazokat. Nagy adathalmazok esetén a bináris keresés hatékonyabb, mint a lineáris keresés. Nézzük táblázatos formában a különbségeket. 
A lineáris és a bináris keresés közötti különbségek
java programozási nyelv oktatóanyaga
Összehasonlítás alapja Lineáris keresés Bináris keresés Meghatározás A lineáris keresés az első elemtől kezdi a keresést, és minden elemet összehasonlít a keresett elemmel, amíg az elem nem található. A keresett elem pozícióját a tömb középső elemének megtalálásával találja meg. Rendezett adatok Lineáris keresésnél az elemeket nem kell rendezett sorrendbe rendezni. A bináris keresés előfeltétele, hogy az elemeket rendezett sorrendbe kell rendezni. Végrehajtás A lineáris keresés bármilyen lineáris adatstruktúrán megvalósítható, például tömbön, linkelt listán stb. A bináris keresés megvalósítása korlátozott, mivel csak azokon az adatstruktúrákon valósítható meg, amelyek kétirányú bejárással rendelkeznek. Megközelítés A szekvenciális megközelítésen alapul. Az oszd meg és uralkodj megközelítésen alapul. Méret Kis méretű adathalmazoknál előnyösebb. Nagy méretű adatkészletek esetén előnyösebb. Hatékonyság Nagy méretű adatkészletek esetén kevésbé hatékony. Hatékonyabb nagy méretű adatkészletek esetén. A legrosszabb esetben Lineáris keresésnél az elem megtalálásának legrosszabb forgatókönyve O(n). A bináris keresés során az elem megtalálásának legrosszabb forgatókönyve az O(log2n). A legjobb forgatókönyv Lineáris keresésnél a lista első elemének megtalálásának legjobb esete az O(1). A bináris keresés során a lista első elemének megtalálásának legjobb esete az O(1). Dimenziós tömb Megvalósítható egy- és többdimenziós tömbön is. Csak többdimenziós tömbön valósítható meg.