TADM2E 4.32

From Algorithm Wiki
Revision as of 18:23, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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.