# 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.