Busqueda Binaria con palabras

[Arcana]

Hola, que tal! Trato de hacer un programa dividido por funciones, tengo un diccionario con la frecuencia en la que aparecen las palabras, y en otro arreglo tengo otras cuantas palabras, necesito checar si las palabras del arreglo szPalabrasSugeridas aparecen en el arreglo szPalabras, si aparece agregar esa palabra y su estadistica a szListaFinal, lo intento hacer por busqueda binaria por que seran mas de 50 000 palabras las que se comparen, pero al momento de compilar el programa se queda parpadeando y no me marca ningun error, alguna sugerencia? Les dejo mi codigo.

Codigo que imprime las palabras

Código:

		//Con esa lista de palabras y el diccionario, recupera las sugerencias
		ListaCandidatas(szPalabrasSugeridas, iNumSugeridas, szPalabras, iEstadisticas, iNumElementos,
			szListaFinal, iPeso, iNumLista);

		//Mostrar las opciones candidatas, por orden de peso(frecuencia)
		printf("Las candidatas son \n");
		for (int j = 0; j < iNumLista; j++)
			printf("%s %i\n", szListaFinal[j], iPeso[j]);

Codigo de la funcion que genera las palabras y las compara

Código:

void	ListaCandidatas(
	char	szPalabrasSugeridas[][TAMTOKEN],	
	int		iNumSugeridas,						
	char	szPalabras[][TAMTOKEN],				
	int		iEstadisticas[],					
	int		iNumElementos,						
	char	szListaFinal[][TAMTOKEN],			
	int		iPeso[],							
	int &	iNumLista)							
{

	 int inf, sup, mitad,i;

	 
	 iNumLista = 0;
	 for (i = 0; i < iNumSugeridas; i++)
	 {
		 inf = 0;
		 sup = iNumElementos;
		 char bandera = 'F';
		 while (inf <= sup)
		 {
			 mitad = (inf + sup) / 2;
			 if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) == 0)
			 {
				 strcpy_s(szListaFinal[i], szPalabras[mitad]);
				 iPeso[i] = iEstadisticas[mitad];
				 iNumLista++;
				 bandera = 'V';
				 break;
			 }
			 if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) > 0)
			 {
				 sup = mitad;
				 mitad = (inf + sup) / 2;
			 }
			 if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) < 0)
			 {
				 inf = mitad;
				 mitad = (inf + sup) / 2;
			 }
		 }
	 }
}

[eferion]

A riesgo de pecar de adivino, si en el bucle

Código C:

while (inf <= sup)
 

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

Código C:

if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) > 0) {
  sup = mitad; // (1)
  mitad = (inf + sup) / 2; //(2)
}
 

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

Código C:

if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) < 0) {
  inf = mitad;
  mitad = (inf + sup) / 2;
}
 

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:

if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) > 0) {   
  if( sup == mitad ) break;
 
  sup = mitad;
  mitad = (inf + sup) / 2;
}
 

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?