Binární vyhledávání

Binární vyhledávání (také metoda půlení intervalu) je vyhledávací algoritmus pro nalezení zadané hodnoty v uspořádaném seznamu(poli) pomocí zkracování seznamu o polovinu v každém kroku. Binární vyhledávání najde medián, porovná jej s hledanou hodnotou a na základě výsledku se rozhodne o pokračování v horní nebo dolní části seznamu stejným způsobem.

Binární vyhledávání je algoritmus s časovou složitostí O(log n).

Napište metodu, která najde ve vstupním poli zadanou hodnotu. Metoda vrátí pozici hledané hodnoty,v případě nenalezení vrátí “-1”

static int Hledej (int[] pole, int hledani,int vlevo,int vpravo) {
 
        int pozice = -1;                            //pocatecni hodnota - neni prvek
        int stred = (vlevo+vpravo)/2;               //urceni stredu        
 
        if (pole[stred]==hledani) return stred+1;   //je uprostred
        if (vlevo==vpravo) return pozice;           //neni tam nikde - pole ma jeden prvek
        else{
            if (pole[stred]<hledani)                //budeme hledat v horni polovine pole
            {
                pozice=Hledej(pole,hledani,stred+1,vpravo);
                return pozice;
            }
            else                                    //budeme hledat v dolni polovine pole
            {
                pozice=Hledej(pole,hledani,vlevo,stred-1);
                return pozice;
            }
            }
 
        }
}