Cod sursa(job #1255001)

Utilizator thebest001Neagu Rares Florian thebest001 Data 3 noiembrie 2014 22:45:35
Problema Cautare binara Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.48 kb
#include <stdio.h>
#include <stdlib.h>

int cautbin(int *a, int n, int x)
{
    int i = 1 << 19, nr = -1;
    while (i)
    {
        if (nr + i < n && a[nr + i] <= x)
            nr += i;
        i>>=1;
    }
    if (nr == -1)
        return -1;
    return nr + 1;
}
int cautbinleft(int *a, int n, int x)
{
    int i = 1 << 19, nr = -1;
    while (i)
    {
        if (nr + i < n && a[nr + i] <= x)
            nr += i;
        i>>=1;
    }
    return nr + 1;
}
int cautbinright(int *a, int n, int x)
{
    int i = 1 << 19, nr = -1;
    while (i)
    {
        if (nr + i < n && a[nr + i] < x)
            nr += i;
        i>>=1;
    }
    return nr + 2;
}
void solve(FILE *in, FILE *out)
{
    int n, i, *a, m;
    fscanf(in, "%d", &n);
    a = malloc(sizeof(int) * n);
    for (i = 0; i < n; i++)
    {
        fscanf(in, "%d", &a[i]);
    }
    fscanf(in, "%d", &m);
    int input, number;
    for (i = 0; i < m; i++)
    {
        fscanf(in, "%d %d", &input, &number);
        switch (input)
        {
        case 0:
            fprintf(out, "%d\n", cautbin(a, n, number));
            break;
        case 1:
            fprintf(out, "%d\n", cautbinleft(a, n, number));
            break;
        case 2:
            fprintf(out, "%d\n", cautbinright(a, n, number));
            break;
        default:
            break;
        }
    }
}

int main()
{
    FILE *in = fopen("cautbin.in", "r");
    FILE *out = fopen("cautbin.out", "w");
    solve(in, out);
    fclose(in);
    fclose(out);
    return 0;
}