I dont understand why you are dividing it by 2. The random search must be
from the whole key space.
>We now have N/2 canidate keys, and the "true" key must be one of them, by
>your reasoning. So why search them all? Let's use your random search on
>these N/2 keys we have selected. Now we're assured of finding the key
>after testing only N/2/2 (N/4) keys. Repeat until you're assured of
>finding the key after testing only 1 key.
I have no idea what you are saying there.
--------------------------
Assume you had 100 keys and the soultions was key 75.
A sequential search from the start would require searching 75% of the
key space.
Randomly searching(no dupes) would statistically require how many keys to
be checked before find the right one? I dunno..Im not a statistician or
anything but I thought it would be 50%. On average..after fifty random
picks...we would hit the right key?
Now if we move the soultion to key 10....the sequential method has to
search only 10% of the space..while the random method stays the same.
Now over many many contest....the sequential method will find it sooner,
later in the middle etc.....but it will 'average' out to be 50%.
We aren't doing lots of contests..we have just this one. We dont know where
the key is. If we use sequential and start at the beginning....and the key
for this 1 contest is at the end....we would have to search alot more.
So we could gamble and hope the this one time the key is closer to the
front than the back and save time, or use the random method at get the 50%.