Algoritmul de căutare binar (Binary Search) în Java

Algoritmul de căutare binară este o metodă eficientă în Java programare, folosită pentru a găsi o anumită valoare într-o matrice sortată. Această abordare împarte continuu matricea în două părți și compară valoarea de căutare cu elementul din mijloc.

Cum funcționează algoritmul de căutare binar

Algoritmul de căutare binar începe prin a compara valoarea de căutare cu elementul din mijloc al matricei. Dacă valoarea de căutare este egală cu elementul din mijloc, algoritmul returnează poziția acelui element. Dacă valoarea de căutare este mai mică decât elementul din mijloc, algoritmul continuă căutarea în jumătatea stângă a matricei. Dacă valoarea de căutare este mai mare, algoritmul continuă căutarea în jumătatea dreaptă a matricei. Acest proces se repetă până când este găsită valoarea de căutare sau nu mai există elemente de căutat.

Avantajele și dezavantajele algoritmului de căutare binar

Avantaje:

• Eficiență ridicată: Acest algoritm elimină jumătate din elemente în fiecare pas, optimizând căutarea matricelor mari.
• Complexitate de timp scăzută: complexitatea de timp a acestui algoritm este O(log n), făcându-l eficient pentru seturi mari de date.

Dezavantaje:

• Cerință pentru matrice sortată: algoritmul funcționează numai cu matrice sortate.

Exemplu și explicație

Luați în considerare un exemplu de utilizare a algoritmului de căutare binar pentru a găsi un anumit întreg într-o matrice de întregi sortate în 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");  
        }  
    }  
}  

În acest exemplu, folosim algoritmul de căutare binar pentru a găsi numărul 9 într-o matrice de întregi sortate. Algoritmul iterează prin matrice și compară valoarea de căutare cu valoarea din mijloc. În acest caz, numărul 9 se găsește la poziția 4(index bazat pe 0) în matrice.

În timp ce acest exemplu demonstrează modul în care algoritmul de căutare binar poate găsi un element într-un tablou întreg sortat, acesta poate fi aplicat și altor scenarii de căutare în Java programare.