4 mai - algoritm de căutare binară + Tema/5

Algoritm de căutare binară

#include<iostream>
using namespace std;
int v[100],n;

int DI(int x, int st, int dr)
{int m;
if(st>dr)
    return -1;
m=(st+dr)/2;
if(v[m]>x)
    return DI(x,st,m-1);
else if(v[m]<x) return DI(x,m+1,dr);
    else return m;

}

int main()
{int i,x;
cout<<"n=";cin>>n;
cout<<"x=";cin>>x;
for(i=0;i<n;i++)
    cin>>v[i];
cout<<DI(x,0,n-1);}

Vom genera aleator un tablou cu 1000 de elemente distincte. Îl vom ordona strict crescător. Elementele tabloului le vom genera între 1 şi 1 milion. Vom căuta în acest şir m numere naturale pe care le vom genera tot aleator. Pentru fiecare număru căutat vom memora numărul de apeluri ale funcţiei de căutare binară.

#include<iostream>
using namespace std;
int a[100],m[100],mm,apel[100]={0},i,nr,limita;

void fort(int x[], int nr, int limita)
{ int u,p=0,i,ok;
    u=rand()%limita+1;
x[0]=u;
p++;
while(p<nr)
{
    ok=0;
    u=rand()%limita+1;
    for(i=0;i<p;i++)
    {
        if(x[i]==u)
            ok=1;
    }
    if(ok==0)
    {
        x[p]=u;
        p++;
    }
}
}

void ordonare(int x[], int n)
{int i,j;
for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
        if(x[i]>x[j])
            swap(x[i],x[j]);
}

int binar(int v[],int x, int st, int dr, int &y)
{int m;
if(st>dr)
    return -1;
m=(st+dr)/2;
if(v[m]>x)
    {y++;return binar(v,x,st,m-1,y);}
else if(v[m]<x) {y++;return binar(v,x,m+1,dr,y);}
    else return m;
}

int main()
{
cout<<"nr de elemente ale vectorului mare=";cin>>nr;
cout<<"limita elementelor generate=";cin>>limita;
fort(a,nr,limita);
ordonare(a,nr);
for(i=0;i<nr;i++)
    cout<<a[i]<<" ";
cout<<endl<<endl<<"nr de elemente ale vectorului mic=";cin>>mm;
fort(m,mm,limita);
ordonare(m,mm);
for(i=0;i<mm;i++)
    cout<<m[i]<<" ";
for(i=0;i<mm;i++)
    binar(a,m[i],0,nr-1,apel[i]);
cout<<endl;
for(i=0;i<mm;i++)
    cout<<"Pentru "<<m[i]<<" au fost necesare "<<apel[i]<<" apeluri"<<endl;
}