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)

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í 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)

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í 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ů

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ů (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ě

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

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