Dvejetainis paieškos (Binary Search) algoritmas Java

Dvejetainės paieškos algoritmas yra efektyvus Java programavimo metodas, naudojamas norint rasti konkrečią reikšmę surūšiuotame masyve. Šis metodas nuolat padalija masyvą į dvi dalis ir lygina paieškos reikšmę su viduriniu elementu.

Kaip veikia dvejetainis paieškos algoritmas

Dvejetainės paieškos algoritmas pradedamas lyginant paieškos reikšmę su viduriniu masyvo elementu. Jei paieškos reikšmė lygi viduriniam elementui, algoritmas grąžina to elemento padėtį. Jei paieškos reikšmė mažesnė už vidurinį elementą, algoritmas tęsia paiešką kairėje masyvo pusėje. Jei paieškos reikšmė didesnė, algoritmas tęsia paiešką dešinėje masyvo pusėje. Šis procesas kartojamas tol, kol randama paieškos reikšmė arba nebelieka ieškomų elementų.

Dvejetainės paieškos algoritmo privalumai ir trūkumai

Privalumai:

• Didelis efektyvumas: šis algoritmas pašalina pusę elementų kiekviename žingsnyje, optimizuodamas didelių masyvų paiešką.
• Mažas laiko sudėtingumas: šio algoritmo laiko sudėtingumas yra O(log n), todėl jis veiksmingas dideliems duomenų rinkiniams.

Trūkumai:

• Rūšiuoto masyvo reikalavimas: algoritmas veikia tik su surūšiuotais masyvais.

Pavyzdys ir paaiškinimas

Apsvarstykite pavyzdį, kaip naudoti dvejetainės paieškos algoritmą, norint rasti konkretų sveikąjį skaičių surūšiuotame sveikųjų skaičių masyve 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");  
        }  
    }  
}  

Šiame pavyzdyje mes naudojame dvejetainės paieškos algoritmą, kad surastume skaičių 9 surūšiuotame sveikųjų skaičių masyve. Algoritmas kartojasi per masyvą ir lygina paieškos reikšmę su vidurine reikšme. Šiuo atveju skaičius 9 yra masyvo 4 pozicijoje(0 pagrindu).

Nors šis pavyzdys parodo, kaip dvejetainės paieškos algoritmas gali rasti elementą surūšiuotame sveikųjų skaičių masyve, jį taip pat galima pritaikyti kitiems paieškos scenarijams programuojant Java.