TADM2E 4.32

From Algorithm Wiki
Jump to: navigation, search

(1) Do a binary search within the range of $ 1-n $. You guess the right number within O(log n) questions.

(2) If you don't know n start with a random number $ 2^i $ and if it is larger than the number you are looking for do a binary search within $ 1-2^i $ as in (1). If $ 2^i $ is less then guess $ 2^{i+1} $ and repeat.