# 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