Binary search – wyszukiwanie binarne – język java
Ja na pierwszym roku studiów musiałem chyba około 3 razy napisać wyszukiwanie binarne na różnego rodzaju laboratoriach poczynając od podstawach programowania, a kończąc na Algorytmach i strukturach danych. Także myślę, że ktoś może z tego przykładu skorzystać. Dodam tylko, że wyszukiwanie binarne można rozwiązać w sposób rekurencyjny. Dość naturalny do wyobrażenia w tym przypadku. Kod poniżej prezentuje właśnie to podejście.
Co do samego algorytmu jak zawsze nie będę się przemęczał (nie dlatego, że mi się nie chce, ale inni opisali go już setki razy)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | public class BinarySearch { public static int tab[] = {3,5,12,20,28,34,38,41,55,67,71,78,81,85,94,99,102}; //funkcja zwraca indeks elementu, jeśli go nie ma zwróci -1 public static int binSearch(int find,int left,int right){ //System.out.println("Szukam "+find+" lewy: "+left+" a prawy: "+right); int index=(left+right)/2; if(tab[index]==find){ return index; } else { if(left>right){ //System.out.println("Nie ma takiej liczby!"); return -1; } else { if(tab[index]<find){ return binSearch(find,index+1,right); } else { return binSearch(find,left,index-1); } } } } public static void main(String[] args){ System.out.println(binSearch(67,0,16)); } } |
Pozdrawiam Piotr!!!
