Obsah

• Srovnávací tabulka
• Definice lineárního vyhledávání
• Definice binárního vyhledávání
• Závěr

Lineární vyhledávání a binární vyhledávání jsou dvě metody, které se používají v polích pro vyhledávání elementy. Hledání je proces nalezení prvku v seznamu prvků uložených v libovolném pořadí nebo náhodně.

Hlavní rozdíl mezi lineárním vyhledáváním a binárním vyhledáváním spočívá v tom, že binární vyhledávání zabere méně času na prohledávání prvku ze tříděného seznamu prvků. Z toho vyplývá, že účinnost metody binárního vyhledávání je větší než lineární vyhledávání.

Další rozdíl mezi těmito dvěma je, že existuje předpoklad pro binární vyhledávání, tj. Prvky musí být tříděné zatímco v lineárním vyhledávání takové předpoklady neexistují. Ačkoli obě metody vyhledávání používají různé techniky, které jsou diskutovány níže.

1. Srovnávací tabulka
2. Definice
3. Klíčové rozdíly
4. Závěr

Srovnávací tabulka

Základ pro srovnání	Lineární vyhledávání	Binární vyhledávání
Časová složitost	NA)	O (log 2 N)
Nejlepší čas na případ	První prvek O (1)	Středový prvek O (1)
Předpoklad pro pole	Není nutné	Pole musí být seřazené
Nejhorší případ pro N počet prvků	Vyžaduje se N srovnání	Lze uzavřít pouze po přihlášení2Srovnání
Lze implementovat na	Pole a propojený seznam	Nelze přímo implementovat do propojeného seznamu
Vložení operace	Snadno vloženo na konec seznamu	Chcete-li zachovat tříděný seznam, je třeba vložit na správné místo zpracování.
Typ algoritmu	Iterativní povaha	Rozdělte a dobývejte v přírodě
Užitečnost	Snadné použití a bez potřeby objednaných prvků.	Každopádně složité algoritmy a prvky by měly být uspořádány v pořádku.
Řádky kódu	Méně	Více

Definice lineárního vyhledávání

Při 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 kontrolováno, zda je to požadovaný prvek nebo ne. Hledání bude neúspěšné, pokud budou přístupné všechny prvky a požadovaný prvek nebude nalezen. V nejhorším případě, číslo průměrného případu, budeme možná muset skenovat polovinu velikosti pole (n / 2).

Proto lze lineární vyhledávání definovat jako techniku, která postupně posouvá pole k nalezení dané položky. Níže uvedený program ilustruje vyhledávání prvku pole pomocí vyhledávání.

Účinnost lineárního vyhledávání

Časová náročnost nebo počet porovnání provedených při prohledávání záznamu v prohledávací tabulce určuje účinnost techniky. Pokud je požadovaný záznam přítomen na první pozici vyhledávací tabulky, provede se pouze jedno porovnání. Pokud je požadovaným záznamem poslední záznam, musí být provedeno n srovnání. Pokud se má záznam objevit někde ve vyhledávací tabulce, bude průměrně počet srovnání (n + 1/2). Nejhorší případová účinnost této techniky je O (n) znamená pořadí provedení.

Program C hledat prvek s technikou lineárního vyhledávání.

#zahrnout #zahrnout void main () {int a, n, i, item, loc = -1; clrscr (); f (" nZadejte číslo prvku:"); scanf ("% d", & n); f ("Zadejte čísla: n"); pro (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nZadejte hledané číslo:"); scanf ("% d", & item); pro (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; přestávka; }} pokud (loc> = 0) {f (" n% d se nachází na pozici% d:", položka, loc + 1); } else {f (" n Položka neexistuje"); } getch (); }

Definice binárního vyhledávání

Binární vyhledávání je velmi 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í. Chcete-li provést binární vyhledávání, musíme nejprve třídit prvky pole.

Logika této techniky je uvedena níže:

• Nejprve vyhledejte střední prvek pole.
• Střední prvek pole je porovnán s hledaným prvkem.

Mohou nastat tři případy:

1. Pokud je prvek požadovaným prvkem, je vyhledávání úspěšné.
2. Pokud je prvek menší než požadovaná položka, prohledejte pouze první polovinu pole.
3. Pokud je větší než požadovaný prvek, pak prohledejte druhou polovinu pole.

Stejné kroky opakujte, dokud se prvek nenajde nebo nevyčerpá v oblasti hledání. V tomto algoritmu se pokaždé zmenšuje oblast hledání. Počet porovnání je tedy maximálně log (N + 1). Výsledkem je efektivní algoritmus ve srovnání s lineárním vyhledáváním, ale pole musí být před provedením binárního vyhledávání tříděno.

Program C najít prvek s technikou binárního vyhledávání.

#zahrnout void main () {int i, beg, end, mid, n, search, array; f ("Zadejte číslo prvku n"); scanf ("% d", & n); f ("Zadejte% d čísla n", n); pro (i = 0; i <n; i ++) scanf ("% d", & pole); f ("Zadejte hledané číslo n"); scanf ("% d", & search); beg = 0; konec = n - 1; prostřední = (žebrání + konec) / 2; while (beg <= end) {if (pole <hledání) beg = middle + 1; else if (array == search) {f ("Hledání bylo úspěšné. n% d nalezeno v umístění% d. n", search, middle + 1); přestávka; } else end = mid - 1; prostřední = (žebrání + konec) / 2; } if (beg> end) f ("Hledání neúspěšné!% d není v seznamu přítomno. n", hledat); getch (); }

1. Lineární vyhledávání je ve své podstatě iterativní a používá sekvenční přístup. Na druhé straně, binární vyhledávání implementuje přístup rozdělit a dobýt.
2. Časová složitost lineárního vyhledávání je O (N), zatímco binární vyhledávání má O (log₂N).
3. Nejlepší čas případu v lineárním vyhledávání je pro první prvek, tj. O (1). Naproti tomu v binárním vyhledávání jde o prostřední prvek, tj. O (1).
4. V lineárním vyhledávání je nejhorším případem pro vyhledávání prvku N počet srovnání. Naopak je to log₂N počet porovnání pro binární vyhledávání.
5. Lineární vyhledávání lze implementovat do pole i do propojeného seznamu, zatímco binární vyhledávání nelze implementovat přímo na propojený seznam.
6. Jak víme, binární vyhledávání vyžaduje seřazené pole, které je důvodem. Aby bylo možné udržovat seřazený seznam, je třeba vložit zpracování na správné místo. Naopak lineární vyhledávání nevyžaduje tříděné prvky, takže se prvky snadno vkládají na konec seznamu.
7. Lineární vyhledávání se snadno používá a není třeba žádných objednaných prvků. Na druhé straně je však 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é jak lineární, tak binární algoritmy vyhledávání. Pokud je pole datovou strukturou a prvky jsou uspořádány v seřazeném pořadí, pak je preferováno binární vyhledávání rychlý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 kvůli nedostupnosti přímé implementace algoritmu binárního vyhledávání.

Typický binární vyhledávací algoritmus nelze použít pro propojený seznam, protože propojený seznam má dynamickou povahu a není známo, kde je prostřední prvek skutečně přiřazen. Existuje tedy požadavek navrhnout variantu binárního vyhledávacího algoritmu, který může pracovat i na propojeném seznamu, protože binární vyhledávání je při provádění rychlejší než lineární vyhledávání.