O problema de busca

Problema: Dado um conjunto S, verificar de um elemento x está ou não em S.

int busca(int *v, int n, int x){
    for(int i=0; i < n; i++){
        if (v[i] == x) return i;
    }

    return -1;
} // Complexidade (O(n))

E se os elementos de S estiverem em ordem crescente?

PROBLEMA: Dado um conjunto S ordenado em ordem crescente, verificar se x pretence a S, devolver a posição que ocupa, ou a posição que deveria ocupar caso contrário. Em outras palavras, dado v[0 ... n-1] e um elemento x, queremos determinar j tal que \(v[j-1] < x <= v[j]\)

Ex.:

n = 8

x = 15

	0	1	2	3	4	5	6	7
v	-3	-1	1	7	10	15	18	21

1ª e = -1; m=(e+d)/2; d=n=8

int buscaBinaria(int *v, int n, int x){
    int e = -1, d = n;
    while(e < d-1){
        int m = (e + d) / 2;
        if(x > v[m]) e = m;
        else d = m;
    }
    return d;
} // Complexidade: O(lg n)