E10.1 Considere a seguinte implementação da busca binária. Diga o que a função faz.
int buscaBinaria (int x, int n, int v[]) {
int e, m, d;
e = 0; d = n-1;
while (e <= d) {
// invariante: v[e-1] < x < v[d+1]
m = (e + d)/2;
if (v[m] == x) return m;
if (v[m] < x) e = m + 1;
else d = m - 1;
}
return -1;
}
Execute buscaBinaria passo-a-passo com n = 14, com x = 9, e com v[i] = i para cada i.
E10.1a Escreva uma versão da função buscaBinaria que tenha o seguinte invariante: no início de cada iteração, v[e-1] < x < v[d].
E10.2 Suponha que o vetor v tem 511 elementos e que x não está no vetor. Quantas vezes, exatamente, a função buscaBinaria comparará x com um elemento do vetor? [Lembre-se da tarefa C (piso de logaritmo).]
Suponha que o vetor v tem 50000 elementos e que x não está no vetor. Quantas vezes, aproximadamente, a função buscaBinaria comparará x com um elemento do vetor?
E10.3 [Tem relação distante com busca binária.] A seguinte função recursiva pretende encontrar o valor de um elemento máximo de v[e..d], supondo e ≤ d. (É claro que não estamos supondo que o vetor está ordenado.)
int max (int e, int d, int v[]) {
if (e == d) return v[d];
else {
int m, x, y;
m = (e + d)/2;
x = max (e, m, v);
y = max (m+1, d, v);
if (x >= y) return x;
else return y;
}
}
A função está correta? Ela é mais rápida que a versão iterativa trivial? Quantas vezes a função chama a si mesma? Suponha que e e d valem 0 e 6 respectivamente e mostre a sequência de chamadas de max, devidamente indentada.
E10.4 Suponha que v[0..n-1] é um vetor de strings em ordem lexicográfica. Escreva uma função que receba uma string x e devolva um índice m tal que a string x é igual à string v[m].
E10.5 Suponha que cada elemento do vetor v[0..n-1] é uma struct com dois campos: o nome de um aluno e o número do aluno. Suponha que o vetor está em ordem crescente de números. Escreva uma função de busca binária que receba o número de um aluno e devolva o seu nome.
E10.6 Como fazer uma busca binária numa lista encadeada?