ani jeden den projít, když nebudeme muset hledat něco v našem každodenním životě, klíče od auta, knihy, pero, nabíječka na mobil a co ne. Stejný je život počítače, je v něm uloženo tolik dat, že kdykoli uživatel požádá o některá data, počítač musí prohledat paměť, aby vyhledal data a zpřístupnil je uživateli. A počítač má vlastní techniky pro rychlé prohledávání paměti, o kterých se můžete dozvědět více v naší sérii výukových programů operačního systému.
co když musíte napsat program pro vyhledávání daného čísla v poli? Jak to uděláš?
No, hledat prvek v daném poli, tam jsou dvě populární algoritmy k dispozici:
- Lineární Vyhledávání
- Binární Vyhledávání
Lineární Vyhledávání
Lineární vyhledávání je velmi základní a jednoduché vyhledávací algoritmus. V lineárním vyhledávání, prohledáváme prvek nebo hodnotu v daném poli procházením pole od začátku, dokud není nalezen požadovaný prvek nebo hodnota.
porovnává prvek, které mají být prohledány všechny prvky přítomné v poli a když prvek je uzavřeno úspěšně, vrátí index prvku v poli, jinak je to návrat -1.
Lineární vyhledávání se používá na netříděných nebo neuspořádaných seznamech, pokud je v seznamu méně prvků.
vlastnosti lineárního vyhledávacího algoritmu
- používá se pro netříděný a neuspořádaný malý seznam prvků.
- má časovou složitost O(n), což znamená, že čas je lineárně závislý na počtu prvků, což není špatné, ale ne tak dobré.
- má velmi jednoduchou implementaci.
algoritmus lineárního vyhledávání implementujeme v dalším tutoriálu.
binární vyhledávání
binární vyhledávání se používá se tříděným polem nebo seznamem. V binárním vyhledávání postupujeme podle následujících kroků:
- začneme porovnáním prohledávaného prvku s prvkem uprostřed seznamu / pole.
- pokud dostaneme shodu, vrátíme index středního prvku.
- pokud nezískáme shodu, zkontrolujeme, zda je hledaný prvek menší nebo větší než hodnota než střední prvek.
- Pokud prvek/číslo, které mají být prohledány je větší hodnota než prostřední číslo, pak jsme se vybrat prvky na pravé straně prostřední prvek(jako seznam/pole je seřazené, proto na pravé straně, budeme mít všechna čísla větší než prostřední číslo), a začněte znovu od kroku 1.
- pokud je hledaný prvek/číslo menší než střední číslo, vybereme prvky na levé straně středního prvku a začneme znovu od kroku 1.
binární vyhledávání je užitečné, pokud je v poli velké množství prvků a jsou seřazeny.
takže nezbytnou podmínkou pro binární vyhledávání je, že seznam/pole by měly být seřazeny.
vlastnosti binárního vyhledávání
- je skvělé prohledávat velká tříděná pole.
- má časovou složitost O (log n), což je velmi dobrá časová složitost. Budeme o tom podrobně diskutovat v tutoriálu binárního vyhledávání.
- má jednoduchou implementaci.