Quickest way to find a number between 0 and 100 if you can verify if it's bigger (or smaller) than another...
If there is a number somewhere between 0 and 100 and you have to find it with the least attempts possible. Every attempt consists of you checking if the number is smaller (or bigger) than a number in the said interval (0 to 100). My guess would be you start with the half way point.
Is it smaller than 50?
yes --> is it smaller than 25---> yes ---> is it smaller than 25 ---> no ---> is it smaller than 37.5 ---> yes...etc
If this is indeed the faster method, what would be the formula that expresses it? If this isn't the fastest method, what is it and how is it expressed mathematically and verbally? Thanks.
integers
add a comment |
If there is a number somewhere between 0 and 100 and you have to find it with the least attempts possible. Every attempt consists of you checking if the number is smaller (or bigger) than a number in the said interval (0 to 100). My guess would be you start with the half way point.
Is it smaller than 50?
yes --> is it smaller than 25---> yes ---> is it smaller than 25 ---> no ---> is it smaller than 37.5 ---> yes...etc
If this is indeed the faster method, what would be the formula that expresses it? If this isn't the fastest method, what is it and how is it expressed mathematically and verbally? Thanks.
integers
add a comment |
If there is a number somewhere between 0 and 100 and you have to find it with the least attempts possible. Every attempt consists of you checking if the number is smaller (or bigger) than a number in the said interval (0 to 100). My guess would be you start with the half way point.
Is it smaller than 50?
yes --> is it smaller than 25---> yes ---> is it smaller than 25 ---> no ---> is it smaller than 37.5 ---> yes...etc
If this is indeed the faster method, what would be the formula that expresses it? If this isn't the fastest method, what is it and how is it expressed mathematically and verbally? Thanks.
integers
If there is a number somewhere between 0 and 100 and you have to find it with the least attempts possible. Every attempt consists of you checking if the number is smaller (or bigger) than a number in the said interval (0 to 100). My guess would be you start with the half way point.
Is it smaller than 50?
yes --> is it smaller than 25---> yes ---> is it smaller than 25 ---> no ---> is it smaller than 37.5 ---> yes...etc
If this is indeed the faster method, what would be the formula that expresses it? If this isn't the fastest method, what is it and how is it expressed mathematically and verbally? Thanks.
integers
integers
asked Nov 26 at 15:18
royale acc
132
132
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
Using the exact halfway point is not the fastest method. For example, suppose the number is $98$. Then you get:
$50 rightarrow 75 rightarrow 87.5 rightarrow 93.75 rightarrow 96.875 rightarrow 98.4375 rightarrow 97.65625$
... and only now you know it is $98$
However, if you use whole numbers, (and let's assume we round down)then you are ruling out those very numbers when it is not that number. So again, if the number is $98$:
$50 rightarrow 75 rightarrow 87 rightarrow 93 rightarrow 96 rightarrow 98$
and now you got it in $6$ ... and if the number was $99$, you'd know it after these $6$ steps as well.
In fact, with this whole number method, it will be true that you will know the number after at most $lfloor log_2 99 rfloor = 6$ steps.
Here is a proof by induction (on $m$) as to why: The general claim is that if you have a choice of $2^m le n < 2^{m+1} $ numbers, it will take at most $lfloor log_2 n rfloor = m$ steps to figure out the number.
Base: $m=0$ ($n=1$)
If there is only $1$ number, you immediately know what that number is, so that takes $0$ steps. And indeed, $lfloor log_2 1 rfloor = 0$
Step:
Suppose you have $2^{m+1} le n < 2^{(m+1)+1} $ numbers left. You pick the halfway number, rounding down if necessary. In the worst case scenario (which is where $n$ is even, and you rounded down for your pick), you are left with exactly $frac{n}{2}$ numbers. Now, given that $2^{m+1} le n < 2^{(m+1)+1} $, we have that $2^m le frac{n}{2} < 2^{m+1}$ and thus, by inductive hypothesis, it takes at most $m$ more steps to figure out the number from this point on. Given that you just took a guess, that means that it takes at most $m+1$ steps to figure out the number, which is what we need to show.
OK, so we have proven that with a choice of $2^m le n < 2^{m+1} $ numbers, it will take at most $lfloor log_2 n rfloor = m$ steps to figure out the number. So, in your case, it takes indeed at most $6$ steps to figure out the number. Since your method of picking the exact halfway point with rounding to a whole number takes $7$ steps in some cases, your method is not the best.
OK, but how do we know that there is not a better method yet, other than using this method of picking the halfway point, and rounding to a whole number? Well, any other method would at some point have to deviate from this method, and thus at some point it would either not pick a whole number (like your original method), or pick a number that would split the leftover numbers in two piles, with one pile at least $2$ larger than the other. But in either case, that means that in the worst case scenario you end up with a pile of numbers that is at least as big as the pile you end up with using the above method.
But if you have more numbers to choose from, it can, in the worst case scenario, never take less steps to figure out the number than when you have fewer numbers, because it that were so, then you could of course figure out the number with the smaller pile in just as few steps by simply adding some extra numbers and making the pile just as big.
So, given that with some alternative method and in the worst case scenario you always get a pile with at least as many numbers as with the above method, this alternative method cannot take any fewer steps in the worst case scenario. Hence, there is no algorithm that has a worst case scenario that has better performance than the above method... meaning that the minimum number of moves in the worst case scenario is indeed $6$.
1
Picking a particular number, and showing that one algorithm is better than another for that particular number, is rather poor reasoning. If we had the number 97, then whole numbers would take seven steps. And your logic for showing that powers of two gives a better average is flimsy at best.
– Acccumulation
Nov 26 at 16:11
@Acccumulation Yeah, I had already realized the powers of $2$ method actually does not give an improvement, so deleted that part already. And you're right, this requires a more solid argument ... will edit! But you know it's $97$ after these $6$ steps ...just as with $99$
– Bram28
Nov 26 at 16:13
@Acccumulation I updated my answer with a proof ...
– Bram28
Nov 26 at 16:32
add a comment |
The other answers have confirmed that this is the best method but did not mention how you can see that you cannot get much better. With $7$ tests and only $2$ possibilities each, there are $2 ^ 7 = 128$ possible result sets so there is some chance of distinguishing $101$ cases if the tests are chosen well. With only $6$ tests, there would be at most $2 ^ 6 = 64$ possible result sets and hence no hope of distinguishing $101$ cases.
I say, "cannot get much better". As I just said, you won't be able to get the worst case below $7$ but, with some tweaking, you might get the average a little lower.
This type of analysis may prove that you cannot do better than a certain number of tests but does not prove that it is possible. For example, suppose there were $3$ possible results to each test $<$, $=$, and $>$ then since $3 ^ 5 > 101$ you might hope that $5$ tests would be sufficient but this alone would not prove it. You would need to find an algorithm with a worst case of $5$ steps or prove it in some other way.
add a comment |
Yes, this is the most efficient search method if you can only get a "yes" or a "no" answer on each attempt. Because there are two possible responses on each attempt, it is known as a binary search - see https://en.wikipedia.org/wiki/Binary_search_algorithm.
No, it is not the most efficient search method, because it uses non-integral values. 37 and 38 are clearly better choices than 37.5, because they allow for an instant win, which 37.5 doesn't.
– TonyK
Nov 26 at 16:14
@TonyK If the only possible responses to "Is it smaller than $x$ ?" are "Yes" and "No" then there are no instant wins - the only way to find $38$ is to narrow the search down to "Smaller than $38$ - No" and "Smaller than $39$ - Yes". If there are $3$ possible responses to each attempt - e.g. "smaller than", "greater than" or "equal to" - then it is no longer a binary search.
– gandalf61
Nov 26 at 17:15
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3014453%2fquickest-way-to-find-a-number-between-0-and-100-if-you-can-verify-if-its-bigger%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
Using the exact halfway point is not the fastest method. For example, suppose the number is $98$. Then you get:
$50 rightarrow 75 rightarrow 87.5 rightarrow 93.75 rightarrow 96.875 rightarrow 98.4375 rightarrow 97.65625$
... and only now you know it is $98$
However, if you use whole numbers, (and let's assume we round down)then you are ruling out those very numbers when it is not that number. So again, if the number is $98$:
$50 rightarrow 75 rightarrow 87 rightarrow 93 rightarrow 96 rightarrow 98$
and now you got it in $6$ ... and if the number was $99$, you'd know it after these $6$ steps as well.
In fact, with this whole number method, it will be true that you will know the number after at most $lfloor log_2 99 rfloor = 6$ steps.
Here is a proof by induction (on $m$) as to why: The general claim is that if you have a choice of $2^m le n < 2^{m+1} $ numbers, it will take at most $lfloor log_2 n rfloor = m$ steps to figure out the number.
Base: $m=0$ ($n=1$)
If there is only $1$ number, you immediately know what that number is, so that takes $0$ steps. And indeed, $lfloor log_2 1 rfloor = 0$
Step:
Suppose you have $2^{m+1} le n < 2^{(m+1)+1} $ numbers left. You pick the halfway number, rounding down if necessary. In the worst case scenario (which is where $n$ is even, and you rounded down for your pick), you are left with exactly $frac{n}{2}$ numbers. Now, given that $2^{m+1} le n < 2^{(m+1)+1} $, we have that $2^m le frac{n}{2} < 2^{m+1}$ and thus, by inductive hypothesis, it takes at most $m$ more steps to figure out the number from this point on. Given that you just took a guess, that means that it takes at most $m+1$ steps to figure out the number, which is what we need to show.
OK, so we have proven that with a choice of $2^m le n < 2^{m+1} $ numbers, it will take at most $lfloor log_2 n rfloor = m$ steps to figure out the number. So, in your case, it takes indeed at most $6$ steps to figure out the number. Since your method of picking the exact halfway point with rounding to a whole number takes $7$ steps in some cases, your method is not the best.
OK, but how do we know that there is not a better method yet, other than using this method of picking the halfway point, and rounding to a whole number? Well, any other method would at some point have to deviate from this method, and thus at some point it would either not pick a whole number (like your original method), or pick a number that would split the leftover numbers in two piles, with one pile at least $2$ larger than the other. But in either case, that means that in the worst case scenario you end up with a pile of numbers that is at least as big as the pile you end up with using the above method.
But if you have more numbers to choose from, it can, in the worst case scenario, never take less steps to figure out the number than when you have fewer numbers, because it that were so, then you could of course figure out the number with the smaller pile in just as few steps by simply adding some extra numbers and making the pile just as big.
So, given that with some alternative method and in the worst case scenario you always get a pile with at least as many numbers as with the above method, this alternative method cannot take any fewer steps in the worst case scenario. Hence, there is no algorithm that has a worst case scenario that has better performance than the above method... meaning that the minimum number of moves in the worst case scenario is indeed $6$.
1
Picking a particular number, and showing that one algorithm is better than another for that particular number, is rather poor reasoning. If we had the number 97, then whole numbers would take seven steps. And your logic for showing that powers of two gives a better average is flimsy at best.
– Acccumulation
Nov 26 at 16:11
@Acccumulation Yeah, I had already realized the powers of $2$ method actually does not give an improvement, so deleted that part already. And you're right, this requires a more solid argument ... will edit! But you know it's $97$ after these $6$ steps ...just as with $99$
– Bram28
Nov 26 at 16:13
@Acccumulation I updated my answer with a proof ...
– Bram28
Nov 26 at 16:32
add a comment |
Using the exact halfway point is not the fastest method. For example, suppose the number is $98$. Then you get:
$50 rightarrow 75 rightarrow 87.5 rightarrow 93.75 rightarrow 96.875 rightarrow 98.4375 rightarrow 97.65625$
... and only now you know it is $98$
However, if you use whole numbers, (and let's assume we round down)then you are ruling out those very numbers when it is not that number. So again, if the number is $98$:
$50 rightarrow 75 rightarrow 87 rightarrow 93 rightarrow 96 rightarrow 98$
and now you got it in $6$ ... and if the number was $99$, you'd know it after these $6$ steps as well.
In fact, with this whole number method, it will be true that you will know the number after at most $lfloor log_2 99 rfloor = 6$ steps.
Here is a proof by induction (on $m$) as to why: The general claim is that if you have a choice of $2^m le n < 2^{m+1} $ numbers, it will take at most $lfloor log_2 n rfloor = m$ steps to figure out the number.
Base: $m=0$ ($n=1$)
If there is only $1$ number, you immediately know what that number is, so that takes $0$ steps. And indeed, $lfloor log_2 1 rfloor = 0$
Step:
Suppose you have $2^{m+1} le n < 2^{(m+1)+1} $ numbers left. You pick the halfway number, rounding down if necessary. In the worst case scenario (which is where $n$ is even, and you rounded down for your pick), you are left with exactly $frac{n}{2}$ numbers. Now, given that $2^{m+1} le n < 2^{(m+1)+1} $, we have that $2^m le frac{n}{2} < 2^{m+1}$ and thus, by inductive hypothesis, it takes at most $m$ more steps to figure out the number from this point on. Given that you just took a guess, that means that it takes at most $m+1$ steps to figure out the number, which is what we need to show.
OK, so we have proven that with a choice of $2^m le n < 2^{m+1} $ numbers, it will take at most $lfloor log_2 n rfloor = m$ steps to figure out the number. So, in your case, it takes indeed at most $6$ steps to figure out the number. Since your method of picking the exact halfway point with rounding to a whole number takes $7$ steps in some cases, your method is not the best.
OK, but how do we know that there is not a better method yet, other than using this method of picking the halfway point, and rounding to a whole number? Well, any other method would at some point have to deviate from this method, and thus at some point it would either not pick a whole number (like your original method), or pick a number that would split the leftover numbers in two piles, with one pile at least $2$ larger than the other. But in either case, that means that in the worst case scenario you end up with a pile of numbers that is at least as big as the pile you end up with using the above method.
But if you have more numbers to choose from, it can, in the worst case scenario, never take less steps to figure out the number than when you have fewer numbers, because it that were so, then you could of course figure out the number with the smaller pile in just as few steps by simply adding some extra numbers and making the pile just as big.
So, given that with some alternative method and in the worst case scenario you always get a pile with at least as many numbers as with the above method, this alternative method cannot take any fewer steps in the worst case scenario. Hence, there is no algorithm that has a worst case scenario that has better performance than the above method... meaning that the minimum number of moves in the worst case scenario is indeed $6$.
1
Picking a particular number, and showing that one algorithm is better than another for that particular number, is rather poor reasoning. If we had the number 97, then whole numbers would take seven steps. And your logic for showing that powers of two gives a better average is flimsy at best.
– Acccumulation
Nov 26 at 16:11
@Acccumulation Yeah, I had already realized the powers of $2$ method actually does not give an improvement, so deleted that part already. And you're right, this requires a more solid argument ... will edit! But you know it's $97$ after these $6$ steps ...just as with $99$
– Bram28
Nov 26 at 16:13
@Acccumulation I updated my answer with a proof ...
– Bram28
Nov 26 at 16:32
add a comment |
Using the exact halfway point is not the fastest method. For example, suppose the number is $98$. Then you get:
$50 rightarrow 75 rightarrow 87.5 rightarrow 93.75 rightarrow 96.875 rightarrow 98.4375 rightarrow 97.65625$
... and only now you know it is $98$
However, if you use whole numbers, (and let's assume we round down)then you are ruling out those very numbers when it is not that number. So again, if the number is $98$:
$50 rightarrow 75 rightarrow 87 rightarrow 93 rightarrow 96 rightarrow 98$
and now you got it in $6$ ... and if the number was $99$, you'd know it after these $6$ steps as well.
In fact, with this whole number method, it will be true that you will know the number after at most $lfloor log_2 99 rfloor = 6$ steps.
Here is a proof by induction (on $m$) as to why: The general claim is that if you have a choice of $2^m le n < 2^{m+1} $ numbers, it will take at most $lfloor log_2 n rfloor = m$ steps to figure out the number.
Base: $m=0$ ($n=1$)
If there is only $1$ number, you immediately know what that number is, so that takes $0$ steps. And indeed, $lfloor log_2 1 rfloor = 0$
Step:
Suppose you have $2^{m+1} le n < 2^{(m+1)+1} $ numbers left. You pick the halfway number, rounding down if necessary. In the worst case scenario (which is where $n$ is even, and you rounded down for your pick), you are left with exactly $frac{n}{2}$ numbers. Now, given that $2^{m+1} le n < 2^{(m+1)+1} $, we have that $2^m le frac{n}{2} < 2^{m+1}$ and thus, by inductive hypothesis, it takes at most $m$ more steps to figure out the number from this point on. Given that you just took a guess, that means that it takes at most $m+1$ steps to figure out the number, which is what we need to show.
OK, so we have proven that with a choice of $2^m le n < 2^{m+1} $ numbers, it will take at most $lfloor log_2 n rfloor = m$ steps to figure out the number. So, in your case, it takes indeed at most $6$ steps to figure out the number. Since your method of picking the exact halfway point with rounding to a whole number takes $7$ steps in some cases, your method is not the best.
OK, but how do we know that there is not a better method yet, other than using this method of picking the halfway point, and rounding to a whole number? Well, any other method would at some point have to deviate from this method, and thus at some point it would either not pick a whole number (like your original method), or pick a number that would split the leftover numbers in two piles, with one pile at least $2$ larger than the other. But in either case, that means that in the worst case scenario you end up with a pile of numbers that is at least as big as the pile you end up with using the above method.
But if you have more numbers to choose from, it can, in the worst case scenario, never take less steps to figure out the number than when you have fewer numbers, because it that were so, then you could of course figure out the number with the smaller pile in just as few steps by simply adding some extra numbers and making the pile just as big.
So, given that with some alternative method and in the worst case scenario you always get a pile with at least as many numbers as with the above method, this alternative method cannot take any fewer steps in the worst case scenario. Hence, there is no algorithm that has a worst case scenario that has better performance than the above method... meaning that the minimum number of moves in the worst case scenario is indeed $6$.
Using the exact halfway point is not the fastest method. For example, suppose the number is $98$. Then you get:
$50 rightarrow 75 rightarrow 87.5 rightarrow 93.75 rightarrow 96.875 rightarrow 98.4375 rightarrow 97.65625$
... and only now you know it is $98$
However, if you use whole numbers, (and let's assume we round down)then you are ruling out those very numbers when it is not that number. So again, if the number is $98$:
$50 rightarrow 75 rightarrow 87 rightarrow 93 rightarrow 96 rightarrow 98$
and now you got it in $6$ ... and if the number was $99$, you'd know it after these $6$ steps as well.
In fact, with this whole number method, it will be true that you will know the number after at most $lfloor log_2 99 rfloor = 6$ steps.
Here is a proof by induction (on $m$) as to why: The general claim is that if you have a choice of $2^m le n < 2^{m+1} $ numbers, it will take at most $lfloor log_2 n rfloor = m$ steps to figure out the number.
Base: $m=0$ ($n=1$)
If there is only $1$ number, you immediately know what that number is, so that takes $0$ steps. And indeed, $lfloor log_2 1 rfloor = 0$
Step:
Suppose you have $2^{m+1} le n < 2^{(m+1)+1} $ numbers left. You pick the halfway number, rounding down if necessary. In the worst case scenario (which is where $n$ is even, and you rounded down for your pick), you are left with exactly $frac{n}{2}$ numbers. Now, given that $2^{m+1} le n < 2^{(m+1)+1} $, we have that $2^m le frac{n}{2} < 2^{m+1}$ and thus, by inductive hypothesis, it takes at most $m$ more steps to figure out the number from this point on. Given that you just took a guess, that means that it takes at most $m+1$ steps to figure out the number, which is what we need to show.
OK, so we have proven that with a choice of $2^m le n < 2^{m+1} $ numbers, it will take at most $lfloor log_2 n rfloor = m$ steps to figure out the number. So, in your case, it takes indeed at most $6$ steps to figure out the number. Since your method of picking the exact halfway point with rounding to a whole number takes $7$ steps in some cases, your method is not the best.
OK, but how do we know that there is not a better method yet, other than using this method of picking the halfway point, and rounding to a whole number? Well, any other method would at some point have to deviate from this method, and thus at some point it would either not pick a whole number (like your original method), or pick a number that would split the leftover numbers in two piles, with one pile at least $2$ larger than the other. But in either case, that means that in the worst case scenario you end up with a pile of numbers that is at least as big as the pile you end up with using the above method.
But if you have more numbers to choose from, it can, in the worst case scenario, never take less steps to figure out the number than when you have fewer numbers, because it that were so, then you could of course figure out the number with the smaller pile in just as few steps by simply adding some extra numbers and making the pile just as big.
So, given that with some alternative method and in the worst case scenario you always get a pile with at least as many numbers as with the above method, this alternative method cannot take any fewer steps in the worst case scenario. Hence, there is no algorithm that has a worst case scenario that has better performance than the above method... meaning that the minimum number of moves in the worst case scenario is indeed $6$.
edited Nov 27 at 12:54
answered Nov 26 at 15:35
Bram28
59.9k44389
59.9k44389
1
Picking a particular number, and showing that one algorithm is better than another for that particular number, is rather poor reasoning. If we had the number 97, then whole numbers would take seven steps. And your logic for showing that powers of two gives a better average is flimsy at best.
– Acccumulation
Nov 26 at 16:11
@Acccumulation Yeah, I had already realized the powers of $2$ method actually does not give an improvement, so deleted that part already. And you're right, this requires a more solid argument ... will edit! But you know it's $97$ after these $6$ steps ...just as with $99$
– Bram28
Nov 26 at 16:13
@Acccumulation I updated my answer with a proof ...
– Bram28
Nov 26 at 16:32
add a comment |
1
Picking a particular number, and showing that one algorithm is better than another for that particular number, is rather poor reasoning. If we had the number 97, then whole numbers would take seven steps. And your logic for showing that powers of two gives a better average is flimsy at best.
– Acccumulation
Nov 26 at 16:11
@Acccumulation Yeah, I had already realized the powers of $2$ method actually does not give an improvement, so deleted that part already. And you're right, this requires a more solid argument ... will edit! But you know it's $97$ after these $6$ steps ...just as with $99$
– Bram28
Nov 26 at 16:13
@Acccumulation I updated my answer with a proof ...
– Bram28
Nov 26 at 16:32
1
1
Picking a particular number, and showing that one algorithm is better than another for that particular number, is rather poor reasoning. If we had the number 97, then whole numbers would take seven steps. And your logic for showing that powers of two gives a better average is flimsy at best.
– Acccumulation
Nov 26 at 16:11
Picking a particular number, and showing that one algorithm is better than another for that particular number, is rather poor reasoning. If we had the number 97, then whole numbers would take seven steps. And your logic for showing that powers of two gives a better average is flimsy at best.
– Acccumulation
Nov 26 at 16:11
@Acccumulation Yeah, I had already realized the powers of $2$ method actually does not give an improvement, so deleted that part already. And you're right, this requires a more solid argument ... will edit! But you know it's $97$ after these $6$ steps ...just as with $99$
– Bram28
Nov 26 at 16:13
@Acccumulation Yeah, I had already realized the powers of $2$ method actually does not give an improvement, so deleted that part already. And you're right, this requires a more solid argument ... will edit! But you know it's $97$ after these $6$ steps ...just as with $99$
– Bram28
Nov 26 at 16:13
@Acccumulation I updated my answer with a proof ...
– Bram28
Nov 26 at 16:32
@Acccumulation I updated my answer with a proof ...
– Bram28
Nov 26 at 16:32
add a comment |
The other answers have confirmed that this is the best method but did not mention how you can see that you cannot get much better. With $7$ tests and only $2$ possibilities each, there are $2 ^ 7 = 128$ possible result sets so there is some chance of distinguishing $101$ cases if the tests are chosen well. With only $6$ tests, there would be at most $2 ^ 6 = 64$ possible result sets and hence no hope of distinguishing $101$ cases.
I say, "cannot get much better". As I just said, you won't be able to get the worst case below $7$ but, with some tweaking, you might get the average a little lower.
This type of analysis may prove that you cannot do better than a certain number of tests but does not prove that it is possible. For example, suppose there were $3$ possible results to each test $<$, $=$, and $>$ then since $3 ^ 5 > 101$ you might hope that $5$ tests would be sufficient but this alone would not prove it. You would need to find an algorithm with a worst case of $5$ steps or prove it in some other way.
add a comment |
The other answers have confirmed that this is the best method but did not mention how you can see that you cannot get much better. With $7$ tests and only $2$ possibilities each, there are $2 ^ 7 = 128$ possible result sets so there is some chance of distinguishing $101$ cases if the tests are chosen well. With only $6$ tests, there would be at most $2 ^ 6 = 64$ possible result sets and hence no hope of distinguishing $101$ cases.
I say, "cannot get much better". As I just said, you won't be able to get the worst case below $7$ but, with some tweaking, you might get the average a little lower.
This type of analysis may prove that you cannot do better than a certain number of tests but does not prove that it is possible. For example, suppose there were $3$ possible results to each test $<$, $=$, and $>$ then since $3 ^ 5 > 101$ you might hope that $5$ tests would be sufficient but this alone would not prove it. You would need to find an algorithm with a worst case of $5$ steps or prove it in some other way.
add a comment |
The other answers have confirmed that this is the best method but did not mention how you can see that you cannot get much better. With $7$ tests and only $2$ possibilities each, there are $2 ^ 7 = 128$ possible result sets so there is some chance of distinguishing $101$ cases if the tests are chosen well. With only $6$ tests, there would be at most $2 ^ 6 = 64$ possible result sets and hence no hope of distinguishing $101$ cases.
I say, "cannot get much better". As I just said, you won't be able to get the worst case below $7$ but, with some tweaking, you might get the average a little lower.
This type of analysis may prove that you cannot do better than a certain number of tests but does not prove that it is possible. For example, suppose there were $3$ possible results to each test $<$, $=$, and $>$ then since $3 ^ 5 > 101$ you might hope that $5$ tests would be sufficient but this alone would not prove it. You would need to find an algorithm with a worst case of $5$ steps or prove it in some other way.
The other answers have confirmed that this is the best method but did not mention how you can see that you cannot get much better. With $7$ tests and only $2$ possibilities each, there are $2 ^ 7 = 128$ possible result sets so there is some chance of distinguishing $101$ cases if the tests are chosen well. With only $6$ tests, there would be at most $2 ^ 6 = 64$ possible result sets and hence no hope of distinguishing $101$ cases.
I say, "cannot get much better". As I just said, you won't be able to get the worst case below $7$ but, with some tweaking, you might get the average a little lower.
This type of analysis may prove that you cannot do better than a certain number of tests but does not prove that it is possible. For example, suppose there were $3$ possible results to each test $<$, $=$, and $>$ then since $3 ^ 5 > 101$ you might hope that $5$ tests would be sufficient but this alone would not prove it. You would need to find an algorithm with a worst case of $5$ steps or prove it in some other way.
answered Nov 26 at 16:02
badjohn
4,2221620
4,2221620
add a comment |
add a comment |
Yes, this is the most efficient search method if you can only get a "yes" or a "no" answer on each attempt. Because there are two possible responses on each attempt, it is known as a binary search - see https://en.wikipedia.org/wiki/Binary_search_algorithm.
No, it is not the most efficient search method, because it uses non-integral values. 37 and 38 are clearly better choices than 37.5, because they allow for an instant win, which 37.5 doesn't.
– TonyK
Nov 26 at 16:14
@TonyK If the only possible responses to "Is it smaller than $x$ ?" are "Yes" and "No" then there are no instant wins - the only way to find $38$ is to narrow the search down to "Smaller than $38$ - No" and "Smaller than $39$ - Yes". If there are $3$ possible responses to each attempt - e.g. "smaller than", "greater than" or "equal to" - then it is no longer a binary search.
– gandalf61
Nov 26 at 17:15
add a comment |
Yes, this is the most efficient search method if you can only get a "yes" or a "no" answer on each attempt. Because there are two possible responses on each attempt, it is known as a binary search - see https://en.wikipedia.org/wiki/Binary_search_algorithm.
No, it is not the most efficient search method, because it uses non-integral values. 37 and 38 are clearly better choices than 37.5, because they allow for an instant win, which 37.5 doesn't.
– TonyK
Nov 26 at 16:14
@TonyK If the only possible responses to "Is it smaller than $x$ ?" are "Yes" and "No" then there are no instant wins - the only way to find $38$ is to narrow the search down to "Smaller than $38$ - No" and "Smaller than $39$ - Yes". If there are $3$ possible responses to each attempt - e.g. "smaller than", "greater than" or "equal to" - then it is no longer a binary search.
– gandalf61
Nov 26 at 17:15
add a comment |
Yes, this is the most efficient search method if you can only get a "yes" or a "no" answer on each attempt. Because there are two possible responses on each attempt, it is known as a binary search - see https://en.wikipedia.org/wiki/Binary_search_algorithm.
Yes, this is the most efficient search method if you can only get a "yes" or a "no" answer on each attempt. Because there are two possible responses on each attempt, it is known as a binary search - see https://en.wikipedia.org/wiki/Binary_search_algorithm.
answered Nov 26 at 15:27
gandalf61
7,673623
7,673623
No, it is not the most efficient search method, because it uses non-integral values. 37 and 38 are clearly better choices than 37.5, because they allow for an instant win, which 37.5 doesn't.
– TonyK
Nov 26 at 16:14
@TonyK If the only possible responses to "Is it smaller than $x$ ?" are "Yes" and "No" then there are no instant wins - the only way to find $38$ is to narrow the search down to "Smaller than $38$ - No" and "Smaller than $39$ - Yes". If there are $3$ possible responses to each attempt - e.g. "smaller than", "greater than" or "equal to" - then it is no longer a binary search.
– gandalf61
Nov 26 at 17:15
add a comment |
No, it is not the most efficient search method, because it uses non-integral values. 37 and 38 are clearly better choices than 37.5, because they allow for an instant win, which 37.5 doesn't.
– TonyK
Nov 26 at 16:14
@TonyK If the only possible responses to "Is it smaller than $x$ ?" are "Yes" and "No" then there are no instant wins - the only way to find $38$ is to narrow the search down to "Smaller than $38$ - No" and "Smaller than $39$ - Yes". If there are $3$ possible responses to each attempt - e.g. "smaller than", "greater than" or "equal to" - then it is no longer a binary search.
– gandalf61
Nov 26 at 17:15
No, it is not the most efficient search method, because it uses non-integral values. 37 and 38 are clearly better choices than 37.5, because they allow for an instant win, which 37.5 doesn't.
– TonyK
Nov 26 at 16:14
No, it is not the most efficient search method, because it uses non-integral values. 37 and 38 are clearly better choices than 37.5, because they allow for an instant win, which 37.5 doesn't.
– TonyK
Nov 26 at 16:14
@TonyK If the only possible responses to "Is it smaller than $x$ ?" are "Yes" and "No" then there are no instant wins - the only way to find $38$ is to narrow the search down to "Smaller than $38$ - No" and "Smaller than $39$ - Yes". If there are $3$ possible responses to each attempt - e.g. "smaller than", "greater than" or "equal to" - then it is no longer a binary search.
– gandalf61
Nov 26 at 17:15
@TonyK If the only possible responses to "Is it smaller than $x$ ?" are "Yes" and "No" then there are no instant wins - the only way to find $38$ is to narrow the search down to "Smaller than $38$ - No" and "Smaller than $39$ - Yes". If there are $3$ possible responses to each attempt - e.g. "smaller than", "greater than" or "equal to" - then it is no longer a binary search.
– gandalf61
Nov 26 at 17:15
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3014453%2fquickest-way-to-find-a-number-between-0-and-100-if-you-can-verify-if-its-bigger%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown