Um vetor v[p..r] é crescente se v[p] ≤ v[p+1] ≤ . . . ≤ v[r]. Um vetor decrescente é definido de maneira análoga. Um vetor está ordenado se for crescente ou decrescente.
Problema: Dado um vetor crescente v[p..r] e um número x, encontrar um índice j no intervalo p..r tal que v[j] == x (ou descobrir que tal índice não existe).
O problema faz sentido quando p ≤ r e até mesmo quando p == r+1. Nesse último caso, dizemos que o vetor é vazio. Em outras palavras, o problema faz sentido quando o vetor tem zero ou mais elementos.
Esta página é um resumo da seção 2.6 (e também da seção 12.4) de Sedgewick.
// A seguinte função recebe um número x e
// um vetor crescente v[p..r] com p <= r+1.
// Ela devolve j em p..r tal que x == v[j].
// Se tal j não existe, devolve -1; essa
// convenção não causa confusão desde que
// -1 não esteja no intervalo p..r.
int buscaSequencial (int x, int v[],
int p, int r) {
int j = p;
while (j <= r && v[j] < x) ++j;
if (j <= r && v[j] == x) return j;
else return -1;
}
Invariante: No começo de cada iteração temos v[j-1] < x. Para que essa afirmação faça sentido no começo da primeira iteração, você deve imaginar que v[p-1] vale − ∞. Isso pode parecer um pouco forçado, mas é razoável pois o vetor é crescente.
Consumo de tempo da função no pior caso: proporcional ao número de elementos do vetor, que é r-p+1. Se o número de elementos dobra, o consumo de tempo também dobra. Se o número de elementos é multiplicado por 10, o consumo de tempo também é multiplicado por 10.
int j, achou = -1; for (j = p; j <= r; j++) if (v[j] == x) achou = j; if (achou == -1) return -1; else return achou;
int j = p; while (v[j] < x && j <= r ) ++j; if (j <= r && v[j] == x) return j; else return -1;
A função abaixo resolve nosso problema de maneira muito mais rápida. Ela foi copiada do Programa 2.2 de Sedgewick.
// A função buscaBinaria recebe um número x
// e um vetor crescente v[p..r] com p <= r+1.
// Ela devolve j em p..r tal que x == v[j].
// Se tal j não existe, devolve -1; essa
// convenção não causará confusão desde que
// -1 não esteja no intervalo p..r.
int buscaBinaria (int x, int v[], int p, int r) {
while (p <= r) {
int m = (p + r)/2;
if (x == v[m]) return m;
if (x < v[m]) r = m - 1;
else p = m + 1;
}
return -1;
}
Qual o invariante do processo iterativo? Para que o invariante fique mais claro, convém reescrever o corpo da função assim:
int pp = p, rr = r;
while (pp <= rr) {
int m = (pp + rr)/2;
if (x == v[m]) return m;
if (x < v[m]) rr = m - 1;
else pp = m + 1;
}
return -1;
Invariante: no começo de cada iteração temos v[pp-1] < x < v[rr+1]. Para que isso faça sentido, é preciso imaginar que v[p-1] vale − ∞ e que v[r+1] vale + ∞.
A função buscaBinaria faz aproximadamente log2 N iterações no pior caso, sendo N = r-p+1 o número de elementos do vetor. Por que? A primeira iteração enfrenta um vetor com N elementos; a segunda, um vetor com N/2 elementos aproximadamente; a terceira, um vetor com N/4 elementos aproximadamente; a i-ésima, um vetor com N/2i-1 elementos aproximadamente. Portanto, o número de iterações é o expoente da maior potência de 2 que fica abaixo de N, ou seja, o número de iterações é aproximadamente log2 N. (A propósito, veja a função lg em outra página.)
O consumo de tempo da função é proporcional ao número de iterações. Portanto, o consumo de tempo é proporcional a log2 N no pior caso. Isso é muito menor que o consumo de tempo da função de busca sequencial pois log transforma multiplicações em somas. Assim, se N é multiplicado por 2, o consumo de tempo apenas aumenta de 1, uma vez que log2 2N = 1 + log2 N. Se N é multiplicado por 16, o consumo de tempo terá apenas 4 unidades a mais. E assim por diante.
int bb (int x, int v[], int p, int r) {
int m;
if (p == r) {
if (v[r] == x) return r;
else return -1;
}
m = (p + r) / 2;
if (v[m] == x) return m;
if (v[m] > x) return bb(x, v, p, m-1);
else return bb(x, v, m+1, r);
}
O programa 12.6 de Sedgewick é uma versão recursiva da busca binária. Veja minha adaptação daquele programa:
int search (int x, int v[], int p, int r) {
int m = (p + r) / 2;
if (p > r) return -1;
if (x == v[m]) return m;
if (x < v[m])
return search(x, v, p, m-1);
else
return search(x, v, m+1, r);
}
Veja a seguinte variação da busca binária que aparece na Figure 4-5 do livro do Roberts:
typedef char *string;
// A função BinarySearch recebe uma string
// key e um vetor array[low..high] de
// strings em ordem lexicográfica. A função
// supõe que low <= high+1. A função
// devolve i tal que as strings key e
// array[i] são iguais, ou seja,
// strcmp(key, array[i]) == 0. A função
// devolve -1 se tal i não existe (a função
// supõe, portanto, que low >= 0
// e high >= 0).
int BinarySearch (string key, string array[],
int low, int high) {
int mid, cmp;
if (low > high) return -1;
mid = (low + high) / 2;
cmp = strcmp(key, array[mid]);
if (cmp == 0) return mid;
if (cmp < 0)
return BinarySearch(key, array, low, mid-1);
else
return BinarySearch(key, array, mid+1, high);
}