Hola lonrot.
Encontrar la *mejor* manera, por ahí es un problema difícil. Sobre todo, no está bien definido (¿estás buscando la manera de asegurarte hacer la menor cantidad de preguntas en el peor caso o aquella que en promedio usa menos preguntas?).
Una buena manera de hacerlo, igual, es ir ubicando los números de a uno, empezando las comparaciones por el centro de la cadena.
Pensé en escribirte un algoritmo en pseudocódigo pero es demasiado trabajo y se va a entender menos que un ejemplo:
La otra persona eligió "42315", nosotros no lo sabemos. (Uso de ahora en mas el símbolo ">" para "está después de")
Preguntamos ¿2>1? No. Anotamos "21"
Preguntamos ¿3>1? No.
Preguntamos ¿3>2? Sí. Anotamos "231" //Esa es la posición relativa de esos tres números.
Preguntamos ¿4>3? No. //Empezamos preguntando por el centro de "231"
// (para que en el peor caso tengamos que preguntar menos)
Preguntamos ¿4>2? No. Anotamos "4231"
Preguntamos ¿5>3? Sí. //"4231" no tiene un número en el centro (como pasaba con"21")
// asi que elegimos uno de los dos lugares vecinos al centro de la lista.
Preguntamos ¿5>1? Sí. Anotamos "42315" y terminamos.
Fíjate que en el paso n haces como máximo Parte_entera_de(n/2) comparaciones.
Así que como máximo haces 1+2+2+3+3=118 preguntas (y el peor caso se alcanza cuando tratas de adivinar "54321"). [corregí la cuenta en esta línea. Gracias manco]
