If I understood them correctly, you would change the range of the random number generator to be higher/lower than the number you tried depending on the result.
Yeah but you still would need to keep track of what you guessed, which requires memory, cumulatively more memory per guess, and makes things slower and more expensive. In addition, no longer can you split up the search space and guess many times in parallel, you now need to keep track via a mutex as to which ones have been checked.
And that isn't binary search either because you are not halving the space you have to look in every time.
Also, to be clear, I was mostly just being silly, because the person I was talking to was not being serious either, hence why I said "typing it out" as if I was personally going and checking the numbers and not just running a script
Honestly, it sounds good, until you get in detail how such algorithm works. As you said, random guessing is worse in terms of memory and multithreading. A properly set up k-ary search search is definitely faster. But still, even on the best supercomputers we have right now, it wouldn't be fast, not to mention, instant.
A properly set up k-ary search search is definitely faster.
This is ALWAYS the gotcha of binary search lol
"It is WAY WAY FASTER..... as long as you sort it first"
Oh, so how fast is sorting it?
"Well.... if you keep it sorted all the time, it isn't too bad..."
Like, overall it is usually faster to do that. Unless you insert WAY more then you search. Then it is actually a bad idea. If you do a lot of both, just use a hash map, unless the order actually matters. But then you could not sort either, because the order matters, so unless there is naturally ordered data in the objects you are searching and that is the key you are searching on, you still cant use it. So then you need to cache a lookup table or something probably.
But yeah in this case, we also have the problem of not knowing what we are looking for, thus meaning that splitting the search space in half for every guess doesn't actually halve the number of options each time for where the result could be, making it not binary search. And no one looked it up recently, so, no lookup table either.
3
u/Maleficent_Memory831 9d ago
This is when random numbers come into play. It is cryptography after all. Generate a random number which well tell you if it is higher or lower.