Difference between revisions of "TADM2E 4.32"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
| − | (1) Do a binary search within the range of | + | (1) Do a binary search within the range of <math>1-n</math>. You guess the right number within O(log n) questions. |
| − | (2) If you don't know n start with a random number | + | (2) If you don't know n start with a random number <math>2^i</math> and if it is larger than the number you are looking for do a binary search within <math>1-2^i</math> as in (1). If <math>2^i</math> is less then guess <math>2^{i+1}</math> and repeat. |
Latest revision as of 18:23, 11 September 2014
(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.
