Cum funcționează algoritmul de căutare binară?

Căutarea binară funcționează analizând un array sortat, împărțind succesiv intervalul de căutare în două.

1. Inițializare: Se definesc limita stângă și dreaptă a intervalului de căutare (de obicei începutul și sfârșitul array-ului).
2. Comparare: Se calculează indicele din mijlocul intervalului. Valoarea de la acest indice este comparată cu elementul căutat.
3. Reducerea intervalului:
   • Dacă valoarea din mijloc corespunde cu cea căutată, elementul a fost găsit.
   • Dacă valoarea din mijloc este mai mare decât cea căutată, căutarea continuă în jumătatea stângă a intervalului. Limita dreaptă se mută la mijloc - 1.
   • Dacă valoarea din mijloc este mai mică decât cea căutată, căutarea continuă în jumătatea dreaptă a intervalului. Limita stângă se mută la mijloc + 1.
4. Repetare: Pașii 2 și 3 se repetă până când elementul este găsit sau intervalul de căutare devine gol.

Complexitatea algoritmului este O(log n), ceea ce este mult mai eficient decât căutarea liniară pentru array-uri mari.

Exemplu de implementare în Python:

def binary_search(arr, target):
    """
    Implementarea căutării binare.
    Primește un array sortat și valoarea căutată.
    Returnează indicele elementului sau -1 dacă nu este găsit.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Calcularea indicelui mijlociu
        mid_val = arr[mid]      # Obținerea valorii din mijloc

        if mid_val == target:
            return mid  # Element găsit
        elif mid_val < target:
            left = mid + 1  # Caută în dreapta
        else: # mid_val > target
            right = mid - 1 # Caută în stânga

    return -1 # Element ne găsit