Verifica daca un numar citit de la tastatura se gaseste sau nu intr-un vector
citit si el de la tastatura.
Nota: Se ordoneaza crescator valorile din vector. Apoi, se lucreaza prin injumatatiri succesive. Mai intai se compara numarul cautat cu elementul din mijloc. Daca este egal cu elementul din mijloc, s-a gasit numarul si programul se termina.
Daca nu este egal, se verifica daca numarul cautat este mai mare decat elementul din mijloc, caz in care cautam mai departe numai in cea de-a doua jumatate. Daca
numarul cautat este mai mic decat elementul din mijloc, cautam mai departe numai in prima jumatate
Răspunsuri la întrebare
Răspuns:
#include <algorithm>
#include <iostream>
bool cautareBinara(int vectorNumere[], int nrCautat, int iStanga, int iDreapta);
int main() {
int vectorNumere[]{1, 55, 2, 3, 77, 13, 4, 8};
int dimensiuneArray{sizeof(vectorNumere) / sizeof(vectorNumere[0])};
/* ordonăm crescător valorile din vector */
std::sort(vectorNumere, vectorNumere + dimensiuneArray);
int nrCautat{55};
std::cout << nrCautat
<< (cautareBinara(vectorNumere, nrCautat, 0, dimensiuneArray - 1)
? " se afla in vector!\n"
: " nu se afla in vector!\n");
nrCautat = 21;
std::cout << nrCautat
<< (cautareBinara(vectorNumere, nrCautat, 0, dimensiuneArray - 1)
? " se afla in vector!\n"
: " nu se afla in vector!\n");
nrCautat = 3;
std::cout << nrCautat
<< (cautareBinara(vectorNumere, nrCautat, 0, dimensiuneArray - 1)
? " se afla in vector!\n"
: " nu se afla in vector!\n");
return 0;
}
bool cautareBinara(int vectorNumere[], int nrCautat, int iStanga, int iDreapta) {
/* dacă ajungem în situația în care iStânga > iDreapta înseamnă că nrCautat nu se află-n vectorNumere */
if (iStanga > iDreapta) return false;
/* calculăm index-ul de mijloc al array-ului */
int iMid{iStanga + ((iDreapta - iStanga) / 2)};
if (vectorNumere[iMid] == nrCautat) {
/* dacă nr. de pe poziția iMid == cu nrCautat returnăm true */
return true;
}
/* dacă nrCautat < nr. de pe poziția iMid căutăm în subarray-ul stâng */
if (nrCautat < vectorNumere[iMid]) {
return cautareBinara(vectorNumere, iStanga, iMid - 1, nrCautat);
}
/* alftfel căutăm în subarray-ul drept */
return cautareBinara(vectorNumere, iMid + 1, iDreapta, nrCautat);
}