Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

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

Cuprinsul lecției

Se încarcă…

Citește și

Câte numere naturale sunt într-un interval dat? (C++)Instrucțiunea de decizie în C++: if, else, switch, caseNumărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Matrice pătratice în C++. Diagonala principală și secundarăComentarii în C++Suma 1 + 2 + 3 + ... + N în C++Maximul și minimul unui vector în C++Numere triunghiulare. Verificarea unui număr triunghiularMatrice în C++. Declararea și parcurgerea tablourilor bidimensionaleInstrucțiunea do while (structuri repetitive)Verifică dacă trei puncte sunt coliniare C++Tipuri de date în C++: numere întregi, reale, caractere și alteleTransformarea unei litere mari în literă mică în C++Al N-lea termen dintr-o progresie geometricăCăutare binară în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Transformarea unui număr din baza 10 în baza 2 în C++Verifică dacă un caracter este literă în C++Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Cel mai mic număr cu suma cifrelor N în C++Bordarea unei matrice în C++Află secolul unui an citit de la tastatură în C++Numărul permutărilor în C++ (formula permutărilor)Cel mai puțin semnificativ bit în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Aria unui triunghi folosind coordonatele acestora în C++Cum să citești și să afișezi în fișiere în C++Citește un șir de caractere cu spații în C++Recursivitate în C++Suma numerelor naturale dintr-un interval dat în C++Do while vs while în C++ - Care e diferența?Numărul combinărilor în C++ (formula combinărilor)Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Afișarea divizorilor primi ai unui număr în C++Verificare dacă șir de caractere este palindrom în C++Inversarea unui șir de caractere în C++Citirea și afișarea matricelor în C++Ce înseamnă endl în C++?Afișarea elementelor unui vector recursiv în C++Suma divizorilor unui număr în C++Verifică dacă un caracter este cifră în C++Interclasarea a doi vectori în C++Complexitatea unui algoritm (timp și spațiu) în C++Numărul de divizori primi ai unui număr în C++Ciurul lui Eratostene în C++Calculul combinărilor de n luate câte k (nCk) în C++Ce este o variabilă unsigned în C++?Maximul și minimul a n valori în C++Al N-lea termen dintr-o progresie aritmeticăRidicarea la putere în timp logaritmic în C++. Exponențiere rapidăRădăcina cubică a unui număr în C++ (cube root)Șirul lui Fibonacci în C++Verifică dacă o literă este vocală în C++Inversarea unui vector în C++Instrucțiunea while (structuri repetitive)Funcții predefinite în C++ (matematice, șiruri de caractere)Operații cu numere mari în C++ - Toate funcțiile explicateFactorialul unui număr în C++Numărul de divizori al unui număr în C++Valoarea absolută (modulul) unui număr în C++Vectorii în C++: citire și afișareVerifică dacă un număr dat este o putere de 2 în C++Suma elementelor unui vector recursiv în C++Ce este o funcție void în C++?Vectori de frecvență (de apariții) în C++Maximul și minimul a două valori în C++Verifică dacă un număr aparține șirului Fibonacci în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorCum să afișezi partea întreagă a unui număr real în C++Cifra maximă și minimă a unui număr în C++Maximul și minimul a trei valori în C++CMMDC recursiv a două numere naturale în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Verifică dacă o literă este mică sau mare în C++Cifra maximă a unui număr recursiv în C++Cel mai frecvent element dintr-un șir în C++Distanța dintre două puncte în C++Numărul de cifre ale factorialului unui numărStructuri repetitive (while, do while, for, etc)Indicatorul lui Euler în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicInterschimbarea a două variabile în C++ (3 metode)Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Verificarea unui an bisect în C++Cel mai semnificativ bit în C++Cifra de control a unui numărGenerarea șirului Fibonacci generalizat în C++Transformarea unei litere mici în literă mare în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Numărul de apariții al unui număr într-un vector în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiInstrucțiunea break (structuri repetitive)Prima cifră a unui număr în C++Cum să calculezi instant 2 la puterea N în C++Numărul minim de peroane pentru o gară în C++Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortSuma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Mediana unui șir de valori în C++Verifică dacă un număr este par sau impar fără modulo în C++Algoritm recursiv pentru căutare binară (clasa a X-a)Transformarea unui număr din baza 2 în baza 10 în C++Vectorii în C++: declarare și parcurgereCodul ASCII (tabel complet)Instrucțiunea continue (structuri repetitive)Aflarea sumei primelor N sume GaussVerificare dacă un număr este palindrom în C++Oglinditul recursiv al unui număr în C++Tipul struct în C++. Ce sunt structurile de date neomogeneAria și circumferința unui cerc în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Funcții în C++. Ce sunt subprogrameleOglinditul unui număr în C++Pointer în C++. Variabile de tipul char * (char steluță)Copiuțe: Cifrele unui numărCea mai lungă secvență de elemente crescătoare în C++Divide et Impera (metodă de programare C++)Verificare număr prim în C++ (Clasa a IX-a)Instrucțiunea for (structuri repetitive)Combinatorică în C++: permutări, aranjamente, combinări și alteleȘiruri de caractere în C++. Tot ce trebuie să știiCe înseamnă variabilă globală și locală în C++?Radicalul unui număr în C++ (rădăcina pătrată)Al N-lea termen Fibonacci în C++

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont