Cod sursa(job #444075)

Utilizator nopiulianGavrila Iulian nopiulian Data 19 aprilie 2010 12:17:18
Problema Cautare binara Scor 0
Compilator cpp Status done
Runda Tema 10D #1 Marime 1.44 kb
#include <stdio.h>
#include <stdlib.h>
#define N 100010.
int v[N];

int bsearch0 (int p, int u, int key) {
int m;

    while (p <= u) {
        m = (p + u) / 2;
        if (v[m] <= key)
            p = m + 1;
        else
            u = m - 1;
    }
    m = (p + u) / 2;
 
    if (v[m] > key) m --;
    if (v[m] == key)
        return m;
return -1;
}
 
int bsearch1 (int p, int u, int key) {
    int m, n = u;
 
    while (p < u){
        m = (p + u) / 2;
        if (v[m] <= key)
            p = m + 1;
        else
            u = m;
    }
 
    m = (p + u) / 2;
    if (v[m] > key)       -- m;    return m;}
 
int bsearch2 (int p, int u, int key) {
    int m;
 
    while (p < u) {
        m = (p + u) / 2;
        if (v[m] < key)
            p = m + 1;
        else
            u = m;
    }
     
    m = (p + u) / 2;
    if (v[m] < key)
       ++ m;
    return m;
}
 
int main () {
    int i, n, m, tip, val;
 
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);
     
    scanf("%d", &m);
 
    while (m --){
          scanf("%d%d", &tip, &val);
         if (tip == 0)
             printf("%d\n", bsearch0(1, n, val));
          if (tip == 1)
             printf("%d\n", bsearch1(1, n, val));
          if (tip == 2)
            printf("%d\n", bsearch2(1, n, val));
    }
    exit(0);
}