Trouver le trésor caché

Question

Supposons que j'essaie de trouver un trésor caché.

Le trésor est caché à une position connue x. Nous savons que la position x du trésor est quelque part sur l'axe entier (en d'autres termes x est un entier). Afin de trouver le trésor, je dois emporter avec moi un détecteur. Le détecteur ne peut repérer le trésor que s'il est au-dessus.

Ma position de départ est le point 0 et je peux me retirer et l'avant jusqu'à ce que je traverse le trésor, afin que mon détecteur puisse le suivre. Je me déplace toujours sur la ligne entière. Quel est le moyen le plus efficace de se déplacer dans l'axe afin de suivre le trésor ?? Je dois trouver un algorithme qui me permet de trouver le trésor en couvrant une distance $ O (| x |) $

Mon approche: Après une certaine considération, je pense que la façon la plus efficace de trouver le trésor est la suivante: à partir de 0 Je me déplace avant jusqu'à ce que j'atteigne le numéro $2$. Puis je recule jusqu'à ce que j'atteigne le numéro $-2^2$. Puis je bouge devant jusqu'à ce que j'atteigne le numéro $2^3$. Puis je reviens jusqu'à ce que j'atteigne le numéro $-2^4$ etc...

Cependant, j'ai des difficultés à prouver qu'il y a une constante $ c $ (pour lequel je dois calculer une limite supérieure) afin que mon algorithme va m'aider à trouver le trésor à $ c | x | $ se déplace tout au plus. Toute aide est très appréciée! Merci d'avance!

PS Je suis nouveau à l'échange de pile informatique, donc je ne suis pas sûr des balises. Corrigez-les ou ajoutez-en plus si nécessaire.