Kuidas töötab binaarotsingu algoritm?

Binārais meklēšana darbojas, analizējot sakārtotu masīvu, pakāpeniski dalot meklēšanas intervālu uz pusēm.

1. Inicializācija: Nosaka kreiso un labo robežu meklēšanas intervālam (parasti masīva sākums un beigas).
2. Salīdzināšana: Aprēķina intervāla vidus indeksu. Šī indeksa vērtība tiek salīdzināta ar meklējamo elementu.
3. Intervāla sašaurināšana:
   • Ja vidējā vērtība sakrīt ar meklējamo, elements ir atrasts.
   • Ja vidējā vērtība ir lielāka par meklējamo, meklēšana turpinās kreisajā intervāla daļā. Labā robeža tiek pārvietota uz vidus-1.
   • Ja vidējā vērtība ir mazāka par meklējamo, meklēšana turpinās labajā intervāla daļā. Kreisā robeža tiek pārvietota uz vidus+1.
4. Atkārtošana: 2. un 3. solis tiek atkārtots līdz elementa atrašanai vai meklēšanas intervāls kļūst tukšs.

Algoritma sarežģītība ir O(log n), kas ir ievērojami efektīvāk par lineāro meklēšanu lieliem masīviem.

Piemērs Python realizācijai:

def binary_search(arr, target):
    """
    Binārās meklēšanas realizācija.
    Pieņem sakārtotu masīvu un meklējamo vērtību.
    Atgriež elementa indeksu vai -1, ja elements nav atrasts.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Aprēķina vidus indeksu
        mid_val = arr[mid]      # Iegūst vērtību vidū

        if mid_val == target:
            return mid  # Elements atrasts
        elif mid_val < target:
            left = mid + 1  # Meklēšana labajā pusē
        else: # mid_val > target
            right = mid - 1 # Meklēšana kreisajā pusē

    return -1 # Elements nav atrasts