Younger, i used to play to this game where you have to guess a number between 1 and 1000 by giving a proposal. If you are wrong, you are being told if the number you are looking for is higher or lower.
The usual method to find the answer is usually to divide by 2 to make two collections of the same amount of numbers:
Example: The number you are looking for is 702 and is supposed to be between 1 and 1000.
500: higher (1000+0)/2 = 0
750: below (1000+500)/2= 750
625: higher (500+750)/2= 625
687: higher (625+750)/2= 687.5
718: below (687+750)/2= 718.5
702: right (687+718)/2 = 702.5
While i am pretty lucky in this example, you can notice that many time i get a number that is odd, so i have to select a number that is not exactly the ideal one.
So i had the idea to improve the method to try to avoid this problem.
Instead i had the idea to start from a binary representation of the number. It is easy to start from a binary representation of the number, because a lower value gives a zero for its range and a higher or equal one will give you a 1 for its range.
binary representation of 702: 1010111110
1 time 512
0 time 256
1 time 128
0 time 64
1 time 32
1 time 16
1 time 8
1 time 4
1 time 2
0 time 1
512+128+32+16+8+4+2=702
512: higher
768: lower
640: higher
704: lower
672: higher
688: higher
696: higher
700: higher
702: ok
If i start with a number that is a power of 2, i can literally retreive the binary representation of the number.
Also notice that in one method i start with 500 and in the other one, i start with 512 and these 2 values are very close.
So does this trick helps to find the number faster ?
I used the following python scripts to find out:
To emulate the division method:
****
def divide(soluce,min,max):
global lower
global higher
mecan=int((min+max)/2)
if (mecan!=soluce):
print (mecan)
if int((max-min)/2)==0:
mecan=mecan+1
if (mecan==soluce):
print (mecan)
return True
if (mecan<soluce):
lower=mecan
return False
if (mecan>soluce):
higher=mecan
return False
****
To emulate the use of power of 2:
****
def power2(soluce,min,max):
global lower
global higher
multi2=1
while ((lower+(multi2*2))<higher):
multi2=multi2*2
mecan=lower+multi2
#print(mecan)
if (mecan!=soluce):
print (mecan)
if (mecan==soluce):
print(mecan)
return True
if (mecan<soluce):
lower=mecan
return False
if (mecan>soluce):
higher=mecan
return False
****
Example of use to find 702 with the power2 function:
****
findme=701
maxi = 1000
mini = 0
global lower
global higher
lower=mini
higher=maxi
itera = 0
success=1
successtot=0
def divide(soluce,min,max):
global lower
global higher
mecan=int((min+max)/2)
if (mecan!=soluce):
print (mecan)
if int((max-min)/2)==0:
mecan=mecan+1
if (mecan==soluce):
print (mecan)
return True
if (mecan<soluce):
lower=mecan
return False
if (mecan>soluce):
higher=mecan
return False
def power2(soluce,min,max):
global lower
global higher
multi2=1
while ((lower+(multi2*2))<higher):
multi2=multi2*2
mecan=lower+multi2
#print(mecan)
if (mecan!=soluce):
print (mecan)
if (mecan==soluce):
print(mecan)
return True
if (mecan<soluce):
lower=mecan
return False
if (mecan>soluce):
higher=mecan
return False
isok=0
while findme<702:
findme=findme+1
itera = itera + 1
while power2(findme,lower,higher)==False:
success=success+1
print(findme)
if success==10:
isok=isok+1
if (findme % 2==1):
print (findme)
#print (findme)
successtot=successtot+success
lower=mini
higher=maxi
success=1
print(successtot)
#print(itera)
#print(isok)
****
Results:
How many attempts do you need to find the result:
1 attempt(s):
divide: 1
power2: 1
2 attempt(s):
divide: 2
power2: 2
3 attempt(s):
divide: 4
power2: 4
4 attempt(s):
divide: 8
power2: 8
5 attempt(s):
divide: 16
power2: 16
6 attempt(s):
divide: 32
power2: 32
7 attempt(s):
divide: 64
power2: 64
8 attempt(s):
divide: 128
power2: 128
9 attempt(s):
divide: 256
power2: 249
10 attempt(s):
divide: 488
power2: 496
11 attempt(s):
divide: 1 (1000)
power2: 0
You can see that at first, the methods have very similar results, but then dividing by 2 gives slightly better results.
One exception: With the code that we use (it rounds number to the lowest value: (1+2)/2 = 1), 1000 is the last value to be found.
This new idea of method doesn't seem to be a real gain.
It is however not so much worse and this method seems like an acceptable replacement if it's method looks more convenient.