Questão nº 72
Questão de Tecnologia da Informação · FGV TCE-SP 2023 (nº 72)
O pseudocódigo apresentado a seguir representa a pesquisa de um elemento em um vetor ordenado, de forma recursiva, segundo o processo conhecido como pesquisa binária.
```
global var
valores: vetor [1..10] de inteiro
função bin (
pos_ini, pos_fim, x: inteiro
)
var
p, v: inteiro
início
se pos_ini > pos_fim então
retorne -1
senão
p <- (pos_ini + pos_fim) / 2
v <- valores[p]
se v = x então
retorne p
senão
se v < x então
retorne bin (p+1, pos_fim, x)
senão
retorne bin (pos_ini, p-1, x)
fim se
fim se
fim se
fim função
```
Considere o conjunto {4, 5, 8, 9, 14, 16, 17, 20, 23, 25} no vetor global valores, índice inicial 1 e final 10, e divisão entre inteiros truncando a parte decimal.
Com a chamada bin (1, 10, 20), o retorno da posição do número 20 ocorre após a função bin ser executada, incluindo a chamada inicial:
- A2 vezes; (alternativa correta)
- B4 vezes;
- C6 vezes;
- D8 vezes;
- E10 vezes.
Resposta comentada
Gabarito Alternativa A
A pesquisa binária é um algoritmo eficiente para encontrar um item em uma lista ordenada, que funciona dividindo repetidamente pela metade a parte da lista onde o item pode estar, eliminando metade dos elementos a cada passo.
(A) Correta: A função bin é executada 2 vezes.
- Chamada inicial:
bin(1, 10, 20).pos_ini = 1,pos_fim = 10,x = 20.p = (1 + 10) / 2 = 5.v = valores[5] = 14.14 < 20é verdadeiro, então chamabin(5+1, 10, 20), ou seja,bin(6, 10, 20).
- Primeira chamada recursiva:
bin(6, 10, 20).pos_ini = 6,pos_fim = 10,x = 20.p = (6 + 10) / 2 = 8.v = valores[8] = 20.20 = 20é verdadeiro, então retornap(que é 8).
A execução da funçãobintermina aqui, com o valor 20 encontrado. Portanto, a função foi executada 2 vezes.
(B) Incorreta: A função não é executada 4 vezes. A busca é rápida devido à divisão pela metade do espaço de busca.
(C) Incorreta: A função não é executada 6 vezes. Este número seria excessivo para uma pesquisa binária em um vetor de 10 elementos.
(D) Incorreta: A função não é executada 8 vezes. Este valor é muito alto para o número de elementos e a eficiência da pesquisa binária.
(E) Incorreta: A função não é executada 10 vezes. Este número seria o máximo de execuções em uma pesquisa linear (sequencial) no pior caso, não em uma pesquisa binária. A armadilha aqui é confundir a eficiência da pesquisa binária com a pesquisa linear, ou contar passos internos em vez de chamadas de função.
Fonte: FGV TCE-SP 2023 Auxiliar Técnico da Fiscalização - TI (Caderno Tipo 1). Reproduzida para fins de estudo.