Cod sursa(job #1152982)

Utilizator valentinpielePiele Valentin valentinpiele Data 25 martie 2014 10:09:10
Problema Cautare binara Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int v[100005], n;
 
int bs1(int q)
{
    int i=0;
	int max;
	max=1<<16;
    while(max)
    {
        if(i+max<=n && v[i+max]<=q)
            i+=max;
        max/=2;
    }
    if(v[i]==q)
        return i;
    return -1;
}
 
int bs2(int q)
{
    int i=0;
	int max;
	max=1<<16;
    while(max)
    {
        if(i+max<=n && v[i+max]<=q)
            i+=max;
        max/=2;
    }
    return i;
}
 
int bs3(int q)
{
    q--;
    int i=0;
	int max;
	max=1<<16;
    while(max)
    {
        if(i+max<=n && v[i+max]<=q)
            i+=max;
        max/=2;
    }
    return i+1;
}
 
 
int main ()
{
    int i;
	int x, y;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    int k;
	f>>k;
    for(i=1;i<=k;i++)
    {
        f>>x>>y;
        if(x==0)
            g<<bs1(y)<<'\n';
        if(x==1)
            g<<bs2(y)<<'\n';
        if(x==2)
            g<<bs3(y)<<'\n';
    }
	return 0;
}