- Fundamentos de ProgramaçãoAlgoritmosAlgoritmos de Busca
- Fundamentos de ProgramaçãoAlgoritmosConstrução de Algoritmos
- Fundamentos de ProgramaçãoEstruturas de DadosEstrutura de Dados: Array
O algoritmo a seguir deve buscar um determinado elemento (variável X) em um conjunto ordenado de N elementos, armazenados contiguamente na memória em um vetor (variável V). Considere que as variáveis imin, imax, imid e N são de números inteiros.
Entrada:
N – Número de elementos da sequência ordenada V.
V – Sequência de elementos ordenados, acessíveis pelas posições de [0,N-1].
X – Valor do elemento a ser consultado no vetor V.
Saída do retorno:
-1 – Caso o elemento X não pertença à sequência ordenada V.
imid – Posição do elemento X na sequência ordenada V.
Este algoritmo possui dois erros.
| 01 | imin ← 0 enquanto imax > imin faça imid ← (imax+imin)/2 imin ← imid + 1 senão se V[imid] > X então imax ← imid + 1 senão retorne imid fim-se fim-se fim-enquanto |
Considere as possíveis alterações:
I - Linha 01: imin ← 1
II - Linha 03: enquanto imax >= imin faça
III - Linha 04: imid ← (imax+imin+1)/2
IV - Linha 06: imin ← imid - 1
V - Linha 09: imax ← imid - 1
Qual das alternativas corrige o algoritmo anterior?