Algoritm recursiv pentru căutare binară (clasa a X-a)

Am învățat în clasa a IX-a despre algoritmul de Căutare binară (mai multe detalii aici). Algoritmul caută într-un mod eficient dacă un element există sau nu într-un șir ordonat crescător, reducând la fiecare pas câte jumătate din elementele șirului rămas.

În această lecție vom discuta despre o implementare recursivă a algoritmului în C++, foarte ușor de înțeles.

Ce este căutarea binară?

Căutarea binară este un algoritm care caută un element într-un șir de valori ordonate (de regulă, crescător). Căutarea se face prin următorul algoritm. Cât timp mai avem elemente:

• Luăm numărul din mijlocul secvenței curente;
• Dacă este egal cu numărul căutat, am găsit numărul și ne oprim;
• Dacă este mai mare decât numărul căutat, atunci automat toate numerele din dreapta elementului din mijlocul șirului vor fi și ele mai mari decât numărul căutat, deci nu trebuie să le mai verificăm și putem reduce șirul în jumătate (luând prima parte);
• Similar, dacă este mai mic decât numărul căutat, luăm a doua jumătate.

Un exemplu concret se găsește la lecția pentru clasa a IX-a, împreună cu grafice.

Înțelegerea algoritmului recursiv

Algoritmul recursiv se bazează pe o funcție (un subprogram). Acest subprogram este recursiv, adică îl vom apela pe el însuși în cadrul său.

Funcția va avea patru parametri: a[], un vector de numere întregi (sau de orice alt tip, în funcție de cerință), împreună cu doi indici st și dr, care marchează pozițiile de început și de final a secvenței curente în care căutăm elementul nostru, precum și valoarea de căutat: x.

Funcția returnează 1, dacă elementul x a fost găsit, respectiv 0 în caz contrar.

Practic, după ce apelăm cautBin(a, 1, n, x), ne așteptăm să primim 1 sau 0 în funcție de existența lui x în a.

Funcția va face următoarele:

• Dacă secvența noastră nu este validă (adică st este mai mare strict decât dr), atunci ne oprim;
• Dacă secvența noastră este de un singur element (st și dr sunt egale), atunci returnăm 1 dacă acest element este egal cu x, sau 0 în caz contrar;
• În caz contrar, dacă secvența noastră are cel puțin două elemente, luăm elementul din mijloc și îl comparăm cu x. În funcție de această comparație, fie returnăm 1 (dacă mijlocul este chiar egal cu x), fie returnăm cautBin(a, st, mij - 1, x), sau cautBin(a, mij + 1, dr, x), după caz (dacă mijlocul este mai mare sau mai mic decât x).

Implementare în C++

Mai jos implementăm căutarea binară în C++ recursiv.

#include <iostream>

using namespace std;

int cautBin(int a[], int st, int dr, int x) {
    //Explicații: infoas.ro
    if(st > dr) return 0;
    if(st == dr) {
        if(a[st] == x) return 1;
        else return 0;
    }
    int mij = (st + dr) / 2;
    if(a[mij] == x) return 1;
    else if(a[mij] < x) return cautBin(a, mij + 1, dr, x);
    else return cautBin(a, st, mij - 1, x);
}

int main()
{
    //Declarăm și citim datele în ordinea: lungimea șirului, elementele șirului și valoarea de căutat
    int a[100], n, x;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> x;

    //Căutăm binar
    if(cautBin(a, 1, n, x) == 1) {
        cout << "Am gasit valoarea " << x << " in sir!";
    } else {
        cout << "Nu am gasit valoarea " << x << " in sir :(";
    }
    return 0;
}

Alte resurse sau bibliografie

• Subprograme
• Căutare binară în C++
• Căutare binară (PbInfo)