Question

Fiind dat un şir ordonat, să se scrie un program recursiv care realizează căutarea binară, prin împărţirea mulţimii iniţiale în două mulţimi care conţin 1/3 respectiv 2/3 din elementele mulţimii iniţiale.

Answer 1

PROGRAM C++

#include <iostream>  

using namespace std;

int cautare_binara(int v[], int dim, int element) {

   int liminf = 0;

   int limsup = dim - 1;

   while (liminf <= limsup) {

       int mij = liminf + (liminf + limsup) / 3;

       if (v[mij] == element)return mij;

       if (v[mij] < element) {

           liminf = mij + 1;

       }

       else {

           limsup = mij - 1;

       }

   }

   return -1;

}

int main() {

   int v[100], n, x;

cout << "Dimensiune vector : ";

cin >> n;

cout << "Introduceti elemente vector CRESCATOR : ";

for (int i = 0; i < n; i++)

 cin >> v[i];

 

   cout << "Element de cautat : ";

   cin >> x;

   cout << "Elementul " << x << " se afla pe pozitia " << cautare_binara(v, n, x);

}

EXPLICATIE :

Programul este identic cu cel al cautarii binare cu exceptia faptului ca "mijlocul" se calculeaza dupa formula " int mij = liminf + (liminf + limsup) / 3 ".

NOTA :

In cazul in care exsita mai multe elemente cu aceasi valoare in sir se va returna pozitia primului gasit.

Am folosit cautarea binara sub forma de functie nerecursiva. In cazul formei recursive schimbarea care trebuie facuta este aceasi.