a595rice.cpp

quarto esempi vari per c++ (schemi base)

// nuovi concetti: ricerca binaria ricorsiva
#include <iostream>

using namespace std;

int ricerca (int [], int, int, int, int&);

int main() {
  const int N = 1000;
  int i, x, pos, a[N];

  for (i=0; i<N; i++)  {
    a[i] = i+1;
    cout << a[i] << " ";
  }
  cout << endl;

  cout << "Introdurre un numero intero: ";
  cin >> x;
  if (ricerca(a,0,N-1,x,pos))
    cout << x << " si trova nell'insieme alla posizione " << (pos+1) << endl;
  else
    cout << x << " non presente nell'insieme!" << endl;
}

  int ricerca (int a[], int min, int max, int val, int& pos) {
    if (min > max)
      return 0;
    pos = (max+min) / 2;
    if (a[pos] == val)
      return 1;
    return (a[pos] > val) ? ricerca(a,min,pos-1,val,pos) :
      ricerca(a,pos+1,max,val,pos);
  }