PUERTA | PUERTA CS 1996 | Pregunta 66

Considere el siguiente programa que intenta ubicar un elemento x en una array ordenada a[ ] usando la búsqueda binaria. Suponga que N>1 . El programa es erróneo. ¿Bajo qué condiciones falla el programa?

var i,j,k: integer;  x: integer;
    a: array; [1....N] of integer;
begin    i:= 1; j:= N;
repeat    
    k:(i+j) div 2;
    if a[k] < x then i:= k 
    else j:= k 
until (a[k] = x) or (i >= j);
    
if (a[k] = x) then
    writeln ('x is in the array')
else
    writeln ('x is not in the array')
end;

(A) x es el último elemento del arreglo a[]
(B) x es mayor que todos los elementos del arreglo a[]
(C) Ambos anteriores
(D) x es menor que el último elemento del arreglo a []

Respuesta: (C)
Explicación: El programa anterior no funciona en los casos en que el elemento a buscar es el último elemento de a[] o mayor que el último elemento (o elemento máximo) en a[]. Para tales casos, el programa entra en un bucle infinito porque a i se le asigna un valor como k en todas las iteraciones, y i nunca se vuelve igual o mayor que j. Entonces, mientras que la condición nunca se vuelve falsa.
Cuestionario de esta pregunta