Algoritam binarnog pretraživanja (Binary Search) u Java

Algoritam binarnog pretraživanja učinkovita je metoda u Java programiranju koja se koristi za pronalaženje određene vrijednosti unutar sortiranog niza. Ovaj pristup kontinuirano dijeli niz na dva dijela i uspoređuje traženu vrijednost sa srednjim elementom.

Kako radi algoritam binarnog pretraživanja

Algoritam binarnog pretraživanja počinje usporedbom tražene vrijednosti sa srednjim elementom niza. Ako je tražena vrijednost jednaka srednjem elementu, algoritam vraća položaj tog elementa. Ako je tražena vrijednost manja od srednjeg elementa, algoritam nastavlja pretragu u lijevoj polovici niza. Ako je tražena vrijednost veća, algoritam nastavlja pretragu u desnoj polovici polja. Ovaj se proces ponavlja sve dok se ne pronađe tražena vrijednost ili dok nema više elemenata za pretraživanje.

Prednosti i nedostaci algoritma binarnog pretraživanja

Prednosti:

• Visoka učinkovitost: ovaj algoritam eliminira polovicu elemenata u svakom koraku, optimizirajući pretraživanje za velike nizove.
• Niska vremenska složenost: vremenska složenost ovog algoritma je O(log n), što ga čini učinkovitim za velike skupove podataka.

Nedostaci:

• Zahtjev za sortirani niz: Algoritam radi samo sa sortiranim nizovima.

Primjer i objašnjenje

Razmotrite primjer korištenja algoritma binarnog pretraživanja za pronalaženje određenog cijelog broja u sortiranom nizu cijelih brojeva u Java.

public class BinarySearchExample {  
    public static int binarySearch(int[] array, int target) {  
        int left = 0;  
        int right = array.length- 1;  
  
        while(left <= right) {  
            int mid = left +(right- left) / 2;  
  
            if(array[mid] == target) {  
                return mid; // Return position if found  
            } else if(array[mid] < target) {  
                left = mid + 1;  
            } else {  
                right = mid- 1;  
            }  
        }  
        return -1; // Return -1 if not found  
    }  
  
    public static void main(String[] args) {  
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15 };  
        int target = 9;  
  
        int position = binarySearch(numbers, target);  
  
        if(position != -1) {  
            System.out.println("Element " + target + " found at position " + position);  
        } else {  
            System.out.println("Element " + target + " not found in the array");  
        }  
    }  
}  

U ovom primjeru koristimo algoritam binarnog pretraživanja za pronalaženje broja 9 u sortiranom nizu cijelih brojeva. Algoritam iterira kroz niz i uspoređuje traženu vrijednost sa srednjom vrijednošću. U ovom slučaju, broj 9 nalazi se na poziciji 4(indeks temeljen na 0) u nizu.

Iako ovaj primjer pokazuje kako algoritam binarnog pretraživanja može pronaći element u sortiranom nizu cijelih brojeva, može se primijeniti i na druge scenarije pretraživanja u Java programiranju.