Kaip veikia dvejetainio paieškos algoritmas?

Dvinarioji paieška veikia analizuojant surūšiuotą masyvą ir nuolat jį dalijant perpus.

1. Inicijavimas: Nustatomos kairės ir dešinės paieškos intervalo ribos (paprastai masyvo pradžia ir pabaiga).
2. Lyginimas: Apskaičiuojamas intervalo vidurio indeksas. Šio indekso reikšmė lyginama su ieškomu elementu.
3. Intervalo mažinimas:
   • Jei vidurio reikšmė sutampa su ieškomu, elementas rastas.
   • Jei vidurio reikšmė didesnė už ieškomą, paieška tęsiasi kairėje intervalo pusėje. Dešinė riba perkelta į vidurį - 1.
   • Jei vidurio reikšmė mažesnė už ieškomą, paieška tęsiasi dešinėje intervalo pusėje. Kairė riba perkelta į vidurį + 1.
4. Pakartojimas: 2 ir 3 žingsniai kartojami tol, kol elementas rastas arba intervalas tampa tuščias.

Algoritmo sudėtingumas yra O(log n), tai daug efektyviau nei linijinis paieška dideliems masyvams.

Python pavyzdys:

def binary_search(arr, target):
    """
    Dvinario paieškos įgyvendinimas.
    Priima surūšiuotą masyvą ir ieškomą reikšmę.
    Grąžina elemento indeksą arba -1, jei nerandama.
    """
    kairė, dešinė = 0, len(arr) - 1

    while kairė <= dešinė:
        vidurys = (kairė + dešinė) // 2  # Vidurio indeksas
        vidurys_reikšmė = arr[vidurys]      # Vidurio reikšmė

        if vidurys_reikšmė == target:
            return vidurys  # Elementas rastas
        elif vidurys_reikšmė < target:
            kairė = vidurys + 1  # Ieškoma dešinėje
        else: # vidurys_reikšmė > target
            dešinė = vidurys - 1 # Ieškoma kairėje

    return -1 # Elementas nerastas