98 lines
7.3 KiB
Markdown
98 lines
7.3 KiB
Markdown
# Vyhledávání
|
||
|
||
- Vyhledávání je velmi často prováděná činnost
|
||
- **Zjišťujeme**, **zda je prvek určité hodnoty** (též prvek s hodnotou klíče) **přítomen v poli**
|
||
- Někdy stačí informace, zda je či není (```true```/```false```)
|
||
- Většinou je potřeba zjistit index, na kterém se hledaný prvek nachází
|
||
- Typ vyhledávání
|
||
- **Neúplné**
|
||
- Nalezneme **první výskyt** prvku
|
||
- **Úplné**
|
||
- Nalezneme **všechny výskyty** prvku
|
||
- Výsledek neúplného vyhledávání
|
||
- Typicky první index od začátku pole, na kterém se prvek nachází (prvek může být v poli obsažen vícekrát), nebo záporná hodnota, pokud se prvek v poli nenachází (typické použití, protože index prvku nemůže být záporný)
|
||
- Pokud je důležité pouze, zda prvek v poli je či není, ale není důležité kde je, je výsledek vyhledávání pouze ```true``` (prvek je obsažen) nebo ```false``` (prvek není obsažen)
|
||
- Výsledek úplného vyhledávání
|
||
- Pole (případně výpis) všech indexů, na kterých se hledaný prvek nachází, nebo prázdné pole, pokud prvek není v poli obsažen
|
||
- Pokud není důležité, na kterých indexech se prvek nachází, ale zajímá nás, kolikrát je v poli obsažen, výsledkem je počet výskytů prvku (0 pokud prvek není obsažen)
|
||
|
||
### Vyhledávání v neseřazené posloupnosti (poli)
|
||
|
||
- Pokud není pole, ve kterém prvek hledáme, seřazené, je jediná možnost sekvenční vyhledávání
|
||
|
||
#### Neúplné sekvenční vyhledávání v poli základních datových typů
|
||
|
||
- Neúplné sekvenční vyhledávání má **složitost Ο(n)**
|
||
- V **nejhorším případě je nutné projít celé pole**, tedy všech n prvků
|
||
- Princip vyhledávání
|
||
- Procházíme pole od začátku do konce a porovnáváme hodnoty prvků pole s hodnotou hledaného prvku
|
||
- Když prvek nalezneme, ukončíme procházení pole a vrátíme index, na kterém jsme prvek nalezli
|
||
- Pokud dojdeme až do konce pole a prvek nenajdeme, vrátíme zápornou hodnotu (typicky ```-1```)
|
||
|
||
#### Neúplné sekvenční vyhledávání v poli objektů
|
||
|
||
- Vyhledávání v poli objektů je velice podobné, jako vyhledávání v poli základních datových typů
|
||
- Pro porovnání ale **nemůžeme použít operátor** „```==```“, protože pro objekty vrací true pouze v případě, že se jedná o stejnou instanci
|
||
- Můžeme **porovnávat přímo jeden či více atributů instance**
|
||
- Můžeme **využít metodu** ```equals()```, **pokud je** v dané třídě **správně implementovaná**
|
||
|
||
#### Úplné sekvenční vyhledávání
|
||
|
||
- Úplné sekvenční vyhledávání má **složitost Ο(n)**
|
||
- V každém případě **je nutné projít celé pole**, tedy všech n prvků
|
||
- Princip vyhledávání
|
||
- **Princip** je **stejný jako u neúplného sekvenčního vyhledávání**, pouze **neukončíme procházení pole při nalezení prvního výskytu** prvku, ale projdeme pole **vždy až do konce**
|
||
- Protože indexů s pozicemi prvků je více, nestačí vrátit jeden index místo jednoho indexu **vrátíme pole s jednotlivými indexy**
|
||
- Délka pole indexů může být maximálně stejná, jako je počet prvků prohledávaného pole a minimálně může být 0, pokud hledaný prvek nebyl v poli nalezen
|
||
- Počet výskytů hledaného prvku v poli (a tedy délku pole indexů) na začátku neznáme
|
||
- Délku pole indexů tedy volíme jako délku prohledávaného pole
|
||
- Délku můžeme po skončení algoritmu zkrátit vytvořením kratší kopie pole na skutečný počet indexů
|
||
|
||
### Vyhledávání v seřazené posloupnosti (poli)
|
||
|
||
- **Pokud je posloupnost seřazená** (předpokládáme vzestupně, ale mohla by být i sestupně), je možné **použít vyhledávání půlením intervalů** (též binární vyhledávání)
|
||
- Sekvenční vyhledávání je možné použít také, stejně jako na neseřazenou posloupnost, ale je podstatně pomalejší, takže není důvod ho používat, pokud je posloupnost seřazená
|
||
- Pokud provádíme vyhledávání opakovaně a pořadí prvků v prohledávaném poli není důležité, vyplatí se pole jednou seřadit a následně opakovaně používat vyhledávání půlením intervalů
|
||
|
||
#### Neúplné vyhledávání půlením intervalů v poli základních datových typů
|
||
|
||
- Neúplné vyhledávání půlením intervalů (binární vyhledávání) má **složitost Ο(log₂n)**
|
||
- Čas vyhledávání tedy roste pouze s logaritmem počtu prvků prohledávaného pole pro **velký počet prvků** prohledávaného pole je **podstatně rychlejší než sekvenční vyhledávání**
|
||
- Princip vyhledávání
|
||
- V každém kroku rozdělíme prohledávaný interval na dvě poloviny a následně hledáme jen v jedné z polovin
|
||
- Zjistíme hodnotu prvku ležícího na prostředním indexu
|
||
- Pokud je rovna hledané hodnotě, algoritmus končí
|
||
- Pokud je větší než hledaná hodnota, hledáme v levé polovině
|
||
- Pokud je menší než hledaná hodnota, hledáme v pravé polovině
|
||
|
||
#### Úplné vyhledávání půlením intervalů
|
||
|
||
- Pokud je hledaný prvek v poli obsažen vícekrát, vyhledávání půlením intervalů najde jeden z výskytů, ale není jasné, který výskyt to je
|
||
- Nalevo i napravo od nalezeného indexu se mohou vyskytovat prvky se stejnou hodnotou
|
||
- Pro úplné vyhledávání je potřeba sekvenčně prohledat pravé i levé okolí nalezeného indexu, dokud se nenarazí na jiný prvek nebo konec či začátek pole
|
||
- Protože stejné prvky jsou v seřazeném poli vždy u sebe, není třeba vracet pole všech indexů, na kterých se hledaný prvek nachází, stačí vrátit první a poslední index
|
||
|
||
#### Metody pro vyhledávání půlením intervalů z Java Core API
|
||
|
||
- Třída ```Arrays``` obsahuje metody pro vyhledávání půlením intervalů
|
||
- Metoda ```Arrays.binarySearch(pole, klíč)```
|
||
- Prohledává celé pole
|
||
- Metoda ```Arrays.binarySearch(pole, od, do, klíč)```
|
||
- Prohledává pouze část pole udanou indexy ```od``` (včetně) a ```do``` (vyjma)
|
||
- Metody jsou překryté pro pole všech základních datových typů a pro pole objektů
|
||
- Prohledávané pole musí být seřazené, typicky vzestupně (typicky knihovní metodou ```Arrays.sort()```)
|
||
- Metoda vrací index nalezeného prvku, nebo zápornou hodnotu, pokud prvek nebyl nalezen
|
||
- Tato hodnota obecně není ```-1``` nutno testovat hodnotu, zda je menší než ```0```, nikoliv rovna ```-1```
|
||
- Absolutní hodnota záporného čísla udává index, na kterém by prvek byl, kdyby v poli byl
|
||
|
||
#### Vyhledávání půlením intervalů v poli objektů
|
||
|
||
- Pokud bychom chtěli použít binární vyhledávání v poli objektů, je nutné určit, podle čeho se mají objekty porovnávat (podle jakého atributu)
|
||
- Je nutné seřadit pole podle tohoto vybraného porovnání a stejné porovnání použít i v algoritmu binárního vyhledávání
|
||
- Nejrozumnější je použít metodu ```compareTo()```, kterou jsme použili při ručním i knihovním řazení
|
||
- Pro správné použití knihovní metody ```Arrays.binarySearch()``` je nezbytné, aby třída, jejíž instance jsou v poli, implementovala rozhraní ```Comparable<Třída>```
|
||
- Hlavička třídy, jejíž instance jsou v prohledávaném poli, musí být ```public Třída implements Comparable<Třída>```
|
||
- Musí obsahovat metodu ```public int compareTo(Třída třída)```
|
||
- Podrobnosti viz předměty KIV/PPA2 a KIV/OOP
|
||
|