Binary Search conditions
up vote
0
down vote
favorite
When solving a search problem with binary search, sometimes the loop condition is while low < hi and sometimes it is while low <= hi.
I try to alternate between these two based on the output I get, but I want to have a better intuition of how to distinguish between two and know when to use which condition.
What is an easy way to choose which condition to use?
search binary-search
asked Nov 12 at 2:59
Dawn17
741414
add a comment |
up vote
0
down vote
favorite
When solving a search problem with binary search, sometimes the loop condition is while low < hi and sometimes it is while low <= hi.
I try to alternate between these two based on the output I get, but I want to have a better intuition of how to distinguish between two and know when to use which condition.
What is an easy way to choose which condition to use?
search binary-search
asked Nov 12 at 2:59
Dawn17
741414
Also posted at computer science. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, you may flag to request migration.
– burnabyRails
Nov 12 at 15:15
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
When solving a search problem with binary search, sometimes the loop condition is while low < hi and sometimes it is while low <= hi.
I try to alternate between these two based on the output I get, but I want to have a better intuition of how to distinguish between two and know when to use which condition.
What is an easy way to choose which condition to use?
search binary-search
asked Nov 12 at 2:59
Dawn17
741414
When solving a search problem with binary search, sometimes the loop condition is while low < hi and sometimes it is while low <= hi.
I try to alternate between these two based on the output I get, but I want to have a better intuition of how to distinguish between two and know when to use which condition.
What is an easy way to choose which condition to use?
search binary-search
search binary-search
asked Nov 12 at 2:59
Dawn17
741414
asked Nov 12 at 2:59
Dawn17
741414
asked Nov 12 at 2:59
Dawn17
741414
asked Nov 12 at 2:59
Dawn17
741414
asked Nov 12 at 2:59
Dawn17
741414
741414
Also posted at computer science. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, you may flag to request migration.
– burnabyRails
Nov 12 at 15:15
add a comment |
Also posted at computer science. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, you may flag to request migration.
– burnabyRails
Nov 12 at 15:15
Also posted at computer science. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, you may flag to request migration.
– burnabyRails
Nov 12 at 15:15
Also posted at computer science. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, you may flag to request migration.
– burnabyRails
Nov 12 at 15:15
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Both of these approaches should ideally solve the problem correctly if properly implemented. Personally I like to follow the low <= hi approach.
Pseudo Code :
while(low <= hi)
int mid = (low + hi)/2;
if(check condition for mid)
result = mid;
hi = mid - 1; or low = mid + 1;
else
low = mid + 1; or hi = mid - 1;
In the above code we check if mid satisfy's the condition of a possible answer to our solution and based on that move either to the left or the right subsequence. Also note that the movement to the left or the right subsequence depends on whether we want to find the maxima or minima for the problem.
answered Nov 19 at 9:28
uSeemSurprised
1,63521017
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
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
,
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%2fstackoverflow.com%2fquestions%2f53255441%2fbinary-search-conditions%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Both of these approaches should ideally solve the problem correctly if properly implemented. Personally I like to follow the low <= hi approach.
Pseudo Code :
while(low <= hi)
int mid = (low + hi)/2;
if(check condition for mid)
result = mid;
hi = mid - 1; or low = mid + 1;
else
low = mid + 1; or hi = mid - 1;
In the above code we check if mid satisfy's the condition of a possible answer to our solution and based on that move either to the left or the right subsequence. Also note that the movement to the left or the right subsequence depends on whether we want to find the maxima or minima for the problem.
answered Nov 19 at 9:28
uSeemSurprised
1,63521017
add a comment |
up vote
0
down vote
Both of these approaches should ideally solve the problem correctly if properly implemented. Personally I like to follow the low <= hi approach.
Pseudo Code :
while(low <= hi)
int mid = (low + hi)/2;
if(check condition for mid)
result = mid;
hi = mid - 1; or low = mid + 1;
else
low = mid + 1; or hi = mid - 1;
In the above code we check if mid satisfy's the condition of a possible answer to our solution and based on that move either to the left or the right subsequence. Also note that the movement to the left or the right subsequence depends on whether we want to find the maxima or minima for the problem.
answered Nov 19 at 9:28
uSeemSurprised
1,63521017
add a comment |
up vote
0
down vote
up vote
0
down vote
Both of these approaches should ideally solve the problem correctly if properly implemented. Personally I like to follow the low <= hi approach.
Pseudo Code :
while(low <= hi)
int mid = (low + hi)/2;
if(check condition for mid)
result = mid;
hi = mid - 1; or low = mid + 1;
else
low = mid + 1; or hi = mid - 1;
In the above code we check if mid satisfy's the condition of a possible answer to our solution and based on that move either to the left or the right subsequence. Also note that the movement to the left or the right subsequence depends on whether we want to find the maxima or minima for the problem.
answered Nov 19 at 9:28
uSeemSurprised
1,63521017
Both of these approaches should ideally solve the problem correctly if properly implemented. Personally I like to follow the low <= hi approach.
Pseudo Code :
while(low <= hi)
int mid = (low + hi)/2;
if(check condition for mid)
result = mid;
hi = mid - 1; or low = mid + 1;
else
low = mid + 1; or hi = mid - 1;
In the above code we check if mid satisfy's the condition of a possible answer to our solution and based on that move either to the left or the right subsequence. Also note that the movement to the left or the right subsequence depends on whether we want to find the maxima or minima for the problem.
answered Nov 19 at 9:28
uSeemSurprised
1,63521017
answered Nov 19 at 9:28
uSeemSurprised
1,63521017
answered Nov 19 at 9:28
uSeemSurprised
1,63521017
answered Nov 19 at 9:28
uSeemSurprised
1,63521017
1,63521017
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53255441%2fbinary-search-conditions%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
Also posted at computer science. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, you may flag to request migration.
– burnabyRails
Nov 12 at 15:15