Tartalom

• Tartalom: Különbség a lineáris és a bináris keresés között
• Összehasonlító táblázat
• Bináris keresés
• Főbb különbségek
• Következtetés
• Magyarázó videó

A különbség a lineáris keresés és a bináris keresés között az, hogy a lineáris keresés során minden elemet ellenőriznek, összehasonlítanak, majd sorba rendeznek, míg a bináris keresés során a válogatandó listát két részre osztják, majd válogatják. A keresés és a válogatás két fő fogalom a számítógépes programozásban. Számos algoritmust használnak keresésre és rendezésre, de a kereséshez és a válogatáshoz leginkább használt algoritmusok a lineáris keresés és a bináris keresés.

A lineáris keresés és a bináris keresés közötti különbség mindkét algoritmus működésében és hatékonyságában rejlik. A bináris keresés sokkal hatékonyabb algoritmus, mint a lineáris keresési algoritmus. Az iteráció vagy az az idő, ami az egyes értékek összehasonlításához a szortírozás előtt kevesebb a bináris keresésben, mint a lineáris keresés.

A lineáris keresés egy nagyon összetett algoritmus, ha egy számban keresni szeretne egy listában, összehasonlítani és néha megismételni a listában szereplő értékek számát. A lista minden elemét egyenként kapja és összehasonlítja a szomszédos elemmel. Az összes elem elérése és ellenőrzése, majd a megfelelő elem megtalálása. Lehet a legrosszabb eset, ha a lista utolsó száma a keresendő szám. A lineáris keresés az a módszer, amellyel a tömb áthalad és létrehozható a keresendő elem. Ha a hatékonyságról beszélünk, akkor a hatékonyság az, ahányszor a programnak futtatnia kell a szám megtalálásához. Ha az első helyen találjuk a keresett számot, akkor csak egy összehasonlítást kell elvégezni, és a dolgokat rendezni kell, de ha nem, akkor újra és újra összehasonlításokat kell végezni, és a memória pazarlásra kerül. Az összehasonlítások száma átlagosan (n + 1/2). És ennek a módszernek a legrosszabb hatékonysága az, ha az O (n) a végrehajtás sorrendjét jelenti.

A lineáris kereséshez képest a bináris keresés nagyon hatékony. Ebben a módszerben a tömb két részre oszlik, és így az összehasonlítások száma nagyon kevés a bináris kereséshez képest. A bináris keresésnél az idő kevesebb a lineáris kereséshez képest. A bináris keresés úgy működik, hogy a tömb középső elemét megtalálja, majd a középső elemet összehasonlítja a tömb egyik részével. Három lehetőség létezik: középső szám lehet a szám, amelyet meg kell találnunk, vagy az a szám, amely kevesebb, mint a középső szám, vagy az a szám, amely nagyobb, mint a középső szám közepe. Az összehasonlítások száma legfeljebb log (N + 1). A bináris keresés a lineáris kereséshez képest hatékony algoritmus a lineáris kereséshez képest, de a tömböt a bináris keresés elvégzése előtt meg kell rendezni.

Tartalom: Különbség a lineáris és a bináris keresés között

• Összehasonlító táblázat
• Bináris keresés
• Főbb különbségek
• Következtetés
• Magyarázó videó

Összehasonlító táblázat

bázis	Lineáris keresés	Bináris keresés
Jelentés	Az egyes elemek lineáris keresését ellenőrzik, összehasonlítják, majd válogatják	Bináris keresés a válogatandó listát két részre osztja, majd rendezi.
Idő komplexitása	A lineáris keresés időbeli összetettsége O (N).	A bináris keresés időbeli összetettsége O (log 2 N)
Az algoritmus típusa	A lineáris keresés iteratív.	A bináris keresés ossza meg és hódítsa meg.
Kód sora	Lineáris keresésben további kódot kell írni.	Egy bináris keresésben kevesebb kódot kell írni.

Lineáris keresés

A lineáris keresés egy nagyon összetett algoritmus, ha egy számban keresni szeretne egy listában, összehasonlítani és néhányszor megismételni a listában szereplő értékek számát. A lista minden elemét egyenként kapja és összehasonlítja a szomszédos elemmel. Az összes elem elérése és ellenőrzése megtörtént, majd a megfelelő elem megtalálható. Lehet a legrosszabb eset, ha a lista utolsó száma a keresendő szám. A lineáris keresés az a módszer, amellyel a tömb áthalad és létrehozható a keresendő elem. Ha a hatékonyságról beszélünk, akkor a hatékonyság az, ahányszor a programnak futtatnia kell a szám megtalálásához. Ha az első helyen találjuk a keresett számot, akkor csak egy összehasonlítást kell elvégezni, és a dolgokat rendezni kell, de ha nem, akkor újra és újra összehasonlításokat kell végezni, és a memória pazarlásra kerül. Az összehasonlítások száma átlagosan (n + 1/2). És ennek a módszernek a legrosszabb hatékonysága az, ha az O (n) a végrehajtás sorrendjét jelenti.

Bináris keresés

A lineáris kereséshez képest a bináris keresés nagyon hatékony. Ebben a módszerben a tömb két részre oszlik, és így az összehasonlítások száma nagyon kevés a bináris kereséshez képest. A bináris keresésnél az idő kevesebb a lineáris kereséshez képest. A bináris keresés úgy működik, hogy a tömb középső eleme megtalálható, majd a középső elemet összehasonlítják a tömb egyik részével.

Három lehetőség létezik: középső szám lehet a szám, amelyet meg kell találnunk, vagy az a szám, amely kevesebb, mint a középső szám, vagy az a szám, amely nagyobb, mint a középső szám közepe. Az összehasonlítások száma legfeljebb log (N + 1). A bináris keresés a lineáris kereséshez képest hatékony algoritmus a lineáris kereséshez képest, de a tömböt a bináris keresés elvégzése előtt meg kell rendezni.

Főbb különbségek

1. Az egyes elemek lineáris keresését ellenőrzik, összehasonlítják, majd sorba rendezik, míg a bináris keresés során a rendezendő listát két részre osztják, majd válogatják.
2. A lineáris keresés időbeli összetettsége 0 (N), míg a bináris keresés időbeli összetettsége O (log₂N).
3. A lineáris keresés iteratív, míg a bináris keresés osztás és meghódítás.
4. A lineáris keresésben több kódot kell írni, míg a bináris keresésben kevesebb kódot kell írni.

Következtetés

A fenti cikkben egyértelmű különbséget látunk a lineáris keresés és a bináris keresés között.

Magyarázó videó