Ver Mensaje Individual
  #2 (permalink)  
Antiguo 22/11/2016, 06:00
eferion
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 5 meses
Puntos: 204
Respuesta: Busqueda Binaria con palabras

A riesgo de pecar de adivino, si en el bucle

Código C:
Ver original
  1. while (inf <= sup)

Acaba resultando que sup==mitad y el código que se ejecuta a continuación es:

Código C:
Ver original
  1. if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) > 0) {
  2.   sup = mitad; // (1)
  3.   mitad = (inf + sup) / 2; //(2)
  4. }

O si resulta que inf==miad y el código que se ejecuta a continuación es:

Código C:
Ver original
  1. if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) < 0) {
  2.   inf = mitad;
  3.   mitad = (inf + sup) / 2;
  4. }

El programa entrará en bucle.

La explicación es la siguiente (me centro en el primer caso ambos casos son idénticos):

Se produce que sup==mitad, luego:
  • el valor de sup no se verá modificado en (1)
  • Como no ha cambiado el valor de sup ni tampoco el de inf, el valor de mitad en (2) tampoco cambiará
  • Como el valor de mitad no cambia, en la siguiente iteración volverás a comprobar las dos mismas palabras que en la iteración anterior.
  • Repite los pasos anteriores cuantas veces quieras hasta que te aburras.
Yo modificaría ese código para que sea capaz de detectar que una palabra no existe. Quizás algo así:

Código C:
Ver original
  1. if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) > 0) {  
  2.   if( sup == mitad ) break;
  3.  
  4.   sup = mitad;
  5.   mitad = (inf + sup) / 2;
  6. }

Y lo mismo para el límite inferior.

Por cierto, si tanto te preocupa el rendimiento como para no hacer una búsqueda lineal... ¿Por qué fuerzas hasta 3 comparaciones de la cadena en cada iteración? ¿No sería más adecuado entonces hacer una única comparación de cadenas y almacenar el resultado para comparar éste en cada uno de los if?
__________________
La ayuda se paga con esfuerzo o con dinero. Si no estás dispuesto a esforzarte y quieres que te hagan los deberes pide presupuesto, al menos así ahorrarás tiempo.