Difference between revisions of "5.3"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
(Created page with "(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 <math>2^...")
 
(No difference)

Latest revision as of 00:54, 21 September 2020

(1) Do a binary search within the range of [math]\displaystyle{ 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 [math]\displaystyle{ 2^i }[/math] and if it is larger than the number you are looking for do a binary search within [math]\displaystyle{ 1-2^i }[/math] as in (1). If [math]\displaystyle{ 2^i }[/math] is less then guess [math]\displaystyle{ 2^{i+1} }[/math] and repeat.


Back to Chapter 5