Algoritmos | Buscando | Pregunta 4

Considere el siguiente programa en C que intenta ubicar un elemento x en una array Y[] mediante la búsqueda binaria. El programa es erróneo. (PUERTA CS 2008)

1.   f(int Y[10], int x) {
2.     int i, j, k;
3.     i = 0; j = 9;
4.     do {
5.             k =  (i + j) /2;
6.             if( Y[k] < x)  i = k; else j = k;
7.         } while(Y[k] != x && i < j);
8.     if(Y[k] == x) printf ("x is in the array ") ;
9.     else printf (" x is not in the array ") ;
10. }

¿En cuál de los siguientes contenidos de Y y x falla el programa?
(A) Y es [1 2 3 4 5 6 7 8 9 10] y x < 10
(B) Y es [1 3 5 7 9 11 13 15 17 19] y x < 1
(C) Y es [2 2 2 2 2 2 2 2 2 2] y x > 2
(D) Y es [2 4 6 8 10 12 14 16 18 20] y 2 < x < 20 y x es par

Respuesta: (C)
Explicación: El programa anterior no funciona para los casos en que el elemento a buscar es el último elemento de Y[] o mayor que el último elemento (o elemento máximo) en Y[]. 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