Trovare il tesoro nascosto

Question

Supponiamo che sto cercando di trovare un tesoro nascosto.

Il tesoro è nascosto in una posizione conosciuta x. Sappiamo che la posizione X del tesoro è da qualche parte sull'asse intero (in altre parole x è un numero intero). Per trovare il tesoro che devo portare con me un rivelatore. Il rivelatore può individuare il tesoro solo se è al di sopra di esso.

La mia posizione di partenza è il punto 0 e posso spostarmi indietro e davanti fino a quando non attraverso il tesoro, in modo che il mio rivelatore possa rintracciarlo. Mi muovo sempre sulla linea intera. Qual è il modo più efficiente per muoversi attraverso l'asse per tracciare il tesoro ?? Devo trovare un algoritmo che mi permetta di trovare il tesoro coprendo una distanza $ O (| x |) $

Il mio approccio: Dopo una certa considerazione, penso che il modo più efficiente per trovare il tesoro sia il seguente: A partire da 0 muovo davanti fino a raggiungere il numero $2$. Poi torno indietro fino a quando non raggiungo il numero $-2^2$. Poi mi muovo davanti fino a raggiungere il numero $2^3$. Poi torno di nuovo fino a quando non raggiungo il numero $-2^4$ e così via...

Tuttavia, ho difficoltà a dimostrare che esiste una costante $ c $ (per il quale devo calcolare un limite superiore) in modo che il mio algoritmo mi aiuti a trovare il tesoro $ c | x | $ si muove al massimo. Ogni aiuto è molto apprezzato! Grazie in anticipo!

PS Sono nuovo allo scambio di stack di informatica, quindi non sono sicuro dei tag. Correggili o aggiungi più se necessario.