Cod sursa(job #1512964)
Utilizator | Muntea Andrei Marius M.Andrei | Data | 28 octombrie 2015 20:26:39 |
---|---|---|---|
Problema | Cautare binara | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.55 kb |
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream q("cautbin.out");
int n,v[100002];
int cautbin0(int x)
{
int mid,low=1,sup=n,p;
p=-1;
while (low<=sup)
{
mid=(low+sup)/2;
if (v[mid]<=x)
{
low=mid+1;
}
else
{
sup=mid-1;
}
if (v[mid]==x)
{
p=mid;
}
}
return p;
}
int cautbin1(int x)
{
int mid,low=1,sup=n,p;
p=-1;
while (low<=sup)
{
mid=(low+sup)/2;
if (v[mid]<=x)
{
low=mid+1;
}
else
{
sup=mid-1;
}
if (v[mid]<=x)
{
p=mid;
}
}
return p;
}
int cautbin2(int x)
{
int mid,low=1,sup=n,p;
p=-1;
while (low<=sup)
{
mid=(low+sup)/2;
if (v[mid]<x)
{
low=mid+1;
}
else
{
sup=mid-1;
}
if (v[mid]>=x)
{
p=mid;
}
}
return p;
}
int main()
{
f>>n;
for (int i=1;i<=n;i++)
{
f>>v[i];
}
int m,x,nr;
f>>m;
for (int i=1;i<=m;i++)
{
f>>nr>>x;
if (nr==0)
{
q<<cautbin0(x)<<"\n";
}
else if (nr==1)
{
q<<cautbin1(x)<<"\n";
}
else
{
q<<cautbin2(x)<<"\n";
}
}
f.close();
q.close();
}