Hlavním rozdílem mezi lineárním vyhledáváním a binárním vyhledáváním je, že binární vyhledávání trvá méně času, než hledá prvek z seřazeného seznamu prvků. Z toho plyne, že účinnost metody binárního vyhledávání je větší než lineární vyhledávání.
Dalším rozdílem mezi nimi je, že existuje předpoklad pro binární vyhledávání, tj. Prvky musí být tříděny, zatímco v lineárním vyhledávání takový předpoklad není. Ačkoli obě metody vyhledávání používají různé techniky, které jsou popsány níže.
Srovnávací graf
| Základ pro srovnání | Lineární vyhledávání | Binární vyhledávání |
|---|---|---|
| Časová složitost | NA) | O (log 2 N) |
| Nejlepší případ | První prvek O (1) | Středový prvek O (1) |
| Předpoklad pro pole | Není nutné | Pole musí být v uspořádaném pořadí |
| Nejhorší případ pro N počet prvků | Vyžaduje se srovnání N | Lze uzavřít pouze po porovnání log 2 N |
| Lze provést na | Pole a propojený seznam | Nelze přímo implementovat do propojeného seznamu |
| Vložení operace | Snadné vložení na konec seznamu | Vyžadovat zpracování pro vložení na správné místo pro udržení tříděného seznamu. |
| Typ algoritmu | Iterativní povaha | Rozdělte a zvítězte v přírodě |
| Užitečnost | Snadné použití a není třeba žádné objednané prvky. | Každopádně složité algoritmy a prvky by měly být organizovány v pořádku. |
| Řádky kódů | Méně | Více |
Definice lineárního vyhledávání
V lineárním vyhledávání je každý prvek pole získáván jeden po druhém v logickém pořadí a kontroluje se, zda je požadovaný prvek nebo ne. Vyhledávání bude neúspěšné, pokud budou všechny prvky přístupné a požadovaný prvek nebyl nalezen. V nejhorším případě, počet průměrných případů, které možná budeme muset skenovat polovinu velikosti pole (n / 2).
Lineární vyhledávání lze tedy definovat jako techniku, která postupuje pole postupně pro vyhledání dané položky. Níže uvedený program ilustruje hledání prvku pole pomocí vyhledávání.
Účinnost lineárního vyhledávání
Časová spotřeba nebo počet porovnávání provedených při vyhledávání záznamu ve vyhledávací tabulce určuje účinnost této techniky. Pokud je požadovaný záznam přítomen v první pozici vyhledávací tabulky, provede se pouze jedno srovnání. Když je požadovaný záznam poslední, musí být provedeno srovnání n. Pokud má být záznam uveden někde ve vyhledávací tabulce, v průměru bude počet porovnání (n + 1/2). Nejhorší efektivita této techniky je O (n) znamená pořadí provedení.
C Program pro vyhledání prvku s technikou lineárního vyhledávání.
#include #include void main () {int a [100], n, i, položka, loc = -1; clrscr (); printf ("Zadejte číslo prvku:"); scanf ("% d", & n); printf ("Zadejte čísla: n"); pro (i = 0; i <= n-1; i ++) {scanf ("% d", a [i]); } printf ("nZadejte číslo, které má být prohledáno:"); scanf ("% d", & položka); pro (i = 0; i = 0) {printf ("n% d se nachází v pozici% d:", položka, loc + 1); } else {printf ("n Položka neexistuje"); } getch (); } Definice binárního vyhledávání
Binární vyhledávání je extrémně efektivní algoritmus. Tato vyhledávací technika spotřebovává méně času při hledání dané položky v minimálním možném srovnání. Abychom provedli binární vyhledávání, musíme nejprve seřadit prvky pole.
Logika této techniky je uvedena níže:
- Nejprve vyhledejte prostřední prvek pole.
- Střední prvek pole je porovnán s hledaným prvkem.
Mohou nastat tři případy:
- Pokud je prvek požadovaným prvkem, je vyhledávání úspěšné.
- Pokud je prvek menší než požadovaná položka, prohledávejte pouze první polovinu pole.
- Pokud je větší než požadovaný prvek, vyhledejte v druhé polovině pole.
Opakujte stejné kroky, dokud nebude nalezen prvek nebo výfuk ve vyhledávací oblasti. V tomto algoritmu se pokaždé zmenší oblast hledání. Proto je počet srovnávání nejvýše log (N + 1). Jako výsledek je to efektivní algoritmus ve srovnání s lineárním vyhledáváním, ale pole musí být tříděno před provedením binárního vyhledávání.
C Program pro vyhledání prvku s technikou binárního vyhledávání.
#include void main () {int i, beg, end, middle, n, search, array [100]; printf ("Zadejte číslo elementu n"); scanf ("% d", & n); printf ("Zadejte% d čísel n", n); pro (i = 0; i <n; i ++) scanf ("% d" a pole [i]); printf ("Zadejte číslo, které má být prohledáno n"); scanf ("% d", & search); beg = 0; end = n - 1; střední = (beg + end) / 2; while (beg <= end) {if (array [middle] end) printf ("Hledání je neúspěšné!% d není v seznamu. \ t getch (); } Klíčové rozdíly mezi lineárním vyhledáváním a binárním vyhledáváním
- Lineární vyhledávání je iterativní povahy a používá sekvenční přístup. Na druhé straně, binární vyhledávání implementuje dělení a dobývání.
- Časová složitost lineárního vyhledávání je O (N), zatímco binární vyhledávání má O (log 2 N).
- Nejvhodnější doba pro lineární vyhledávání je pro první prvek, tj. O (1). Jako v případě binárního vyhledávání je to pro prostřední prvek, tj. O (1).
- V lineárním hledání je nejhorším případem pro hledání elementu N srovnání. Naproti tomu je log 2 N číslo porovnání pro binární vyhledávání.
- Lineární vyhledávání lze implementovat do pole, stejně jako do propojeného seznamu, zatímco binární vyhledávání nelze implementovat přímo na odkazovaný seznam.
- Jak víme, binární vyhledávání vyžaduje tříděné pole, které je důvodem Vyžaduje zpracování pro vložení na správné místo pro udržení tříděného seznamu. Naopak lineární vyhledávání nevyžaduje tříděné prvky, takže prvky se snadno vkládají na konec seznamu.
- Lineární vyhledávání je snadno použitelné a není třeba žádné objednané prvky. Na druhé straně je algoritmus binárního vyhledávání složitý a prvky jsou nutně uspořádány v pořadí.
Závěr
V závislosti na aplikaci mohou být užitečné lineární i binární vyhledávací algoritmy. Pokud je pole datovou strukturou a prvky jsou uspořádány v uspořádaném pořadí, je pro rychlé vyhledávání preferováno binární vyhledávání. Pokud je propojený seznam datovou strukturou bez ohledu na to, jak jsou prvky uspořádány, je lineární vyhledávání přijato z důvodu nedostupnosti přímé implementace binárního vyhledávacího algoritmu.
Typický algoritmus pro vyhledávání v binárním režimu nelze použít pro propojený seznam, protože propojený seznam má dynamickou povahu a není znám, kde je střední prvek skutečně přiřazen. Existuje tedy požadavek navrhnout variantu binárního vyhledávacího algoritmu, který může pracovat také na propojeném seznamu, protože binární vyhledávání je rychlejší než provádění lineárního vyhledávání.
