Finding the maximum of a bitonic sequence
$begingroup$
Given to us is an array $B[1],ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ {1, dots , n}$ such that $$B[1] < B[2] < dots < B[i^*− 1] < B[i^*] > B[i^* + 1] > B[i^* + 2] > dots > B[n].$$
It is noted that the index $i^*$ is not given as part of the input.
The question asks me to design an algorithm for computing the index $i^*$, whilst trying to ensure it has the smallest running time possible.
I just wondered if anyone could produce this algorithm and explain your thought process on how you came up with it if possible? Stuck on these type of questions
algorithms arrays discrete-mathematics
edited Feb 7 at 4:46
Yuval Filmus
195k14184349
asked Feb 7 at 3:01
opp333opp333
134
$endgroup$
add a comment |
$begingroup$
Given to us is an array $B[1],ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ {1, dots , n}$ such that $$B[1] < B[2] < dots < B[i^*− 1] < B[i^*] > B[i^* + 1] > B[i^* + 2] > dots > B[n].$$
It is noted that the index $i^*$ is not given as part of the input.
The question asks me to design an algorithm for computing the index $i^*$, whilst trying to ensure it has the smallest running time possible.
I just wondered if anyone could produce this algorithm and explain your thought process on how you came up with it if possible? Stuck on these type of questions
algorithms arrays discrete-mathematics
edited Feb 7 at 4:46
Yuval Filmus
195k14184349
asked Feb 7 at 3:01
opp333opp333
134
$endgroup$
1
$begingroup$
Has been asked before. Use some sort of binary search.
$endgroup$
– Yuval Filmus
Feb 7 at 3:16
$begingroup$
Could you link me to the question and yes, thanks
$endgroup$
– opp333
Feb 7 at 3:48
$begingroup$
stackoverflow.com/questions/39185197/…
$endgroup$
– Yuval Filmus
Feb 7 at 4:18
add a comment |
$begingroup$
Given to us is an array $B[1],ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ {1, dots , n}$ such that $$B[1] < B[2] < dots < B[i^*− 1] < B[i^*] > B[i^* + 1] > B[i^* + 2] > dots > B[n].$$
It is noted that the index $i^*$ is not given as part of the input.
The question asks me to design an algorithm for computing the index $i^*$, whilst trying to ensure it has the smallest running time possible.
I just wondered if anyone could produce this algorithm and explain your thought process on how you came up with it if possible? Stuck on these type of questions
algorithms arrays discrete-mathematics
edited Feb 7 at 4:46
Yuval Filmus
195k14184349
asked Feb 7 at 3:01
opp333opp333
134
$endgroup$
Given to us is an array $B[1],ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ {1, dots , n}$ such that $$B[1] < B[2] < dots < B[i^*− 1] < B[i^*] > B[i^* + 1] > B[i^* + 2] > dots > B[n].$$
It is noted that the index $i^*$ is not given as part of the input.
The question asks me to design an algorithm for computing the index $i^*$, whilst trying to ensure it has the smallest running time possible.
I just wondered if anyone could produce this algorithm and explain your thought process on how you came up with it if possible? Stuck on these type of questions
algorithms arrays discrete-mathematics
algorithms arrays discrete-mathematics
edited Feb 7 at 4:46
Yuval Filmus
195k14184349
asked Feb 7 at 3:01
opp333opp333
134
edited Feb 7 at 4:46
Yuval Filmus
195k14184349
asked Feb 7 at 3:01
opp333opp333
134
edited Feb 7 at 4:46
Yuval Filmus
195k14184349
edited Feb 7 at 4:46
Yuval Filmus
195k14184349
edited Feb 7 at 4:46
Yuval Filmus
195k14184349
195k14184349
asked Feb 7 at 3:01
opp333opp333
134
asked Feb 7 at 3:01
opp333opp333
134
asked Feb 7 at 3:01
opp333opp333
134
134
1
$begingroup$
Has been asked before. Use some sort of binary search.
$endgroup$
– Yuval Filmus
Feb 7 at 3:16
$begingroup$
Could you link me to the question and yes, thanks
$endgroup$
– opp333
Feb 7 at 3:48
$begingroup$
stackoverflow.com/questions/39185197/…
$endgroup$
– Yuval Filmus
Feb 7 at 4:18
add a comment |
1
$begingroup$
Has been asked before. Use some sort of binary search.
$endgroup$
– Yuval Filmus
Feb 7 at 3:16
$begingroup$
Could you link me to the question and yes, thanks
$endgroup$
– opp333
Feb 7 at 3:48
$begingroup$
stackoverflow.com/questions/39185197/…
$endgroup$
– Yuval Filmus
Feb 7 at 4:18
1
1
$begingroup$
Has been asked before. Use some sort of binary search.
$endgroup$
– Yuval Filmus
Feb 7 at 3:16
$begingroup$
Has been asked before. Use some sort of binary search.
$endgroup$
– Yuval Filmus
Feb 7 at 3:16
$begingroup$
Could you link me to the question and yes, thanks
$endgroup$
– opp333
Feb 7 at 3:48
$begingroup$
Could you link me to the question and yes, thanks
$endgroup$
– opp333
Feb 7 at 3:48
$begingroup$
stackoverflow.com/questions/39185197/…
$endgroup$
– Yuval Filmus
Feb 7 at 4:18
$begingroup$
stackoverflow.com/questions/39185197/…
$endgroup$
– Yuval Filmus
Feb 7 at 4:18
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The first thing that comes to my mind after reading your question is as follow. Draw the sequence as a graph given below. Each $B[i]$ you can think of a point in the graph given below.
The idea to do binary search should be clear from the question as input sequence is almost sorted. Now if you guess the peak point then you are in a good position, but during the binary search if you choose a number which will give you two cases.
The above two cases are the cases in which you need to think, but if you have tried few problems on binary search then now the problem will be easy to solve. More formally you can see the yuval's answer. You ask for the thought process, I have tried to give you my thought process. For any two persons thought process is different, there may be many other way to visualise the problem you have described.
answered Feb 7 at 7:25
aaagaaag
1,142418
$endgroup$
add a comment |
$begingroup$
A sequence satisfying your constraint is known as bitonic. (Strictly speaking, a bitonic sequence is one which is either monotone increasing then decreasing or monotone decreasing then increasing). You can find the index $i^*$ using binary search. The idea is that given an index $i$, you can compare $i$ to $i^*$ as follows:
- If $B[i-1] < B[i] > B[i+1]$, then $i = i^*$.
- If $B[i-1] < B[i] < B[i+1]$, then $i < i^*$.
- If $B[i-1] > B[i] > B[i+1]$, then $i > i^*$.
I'll leave you to handle the corner cases $i = 1$ and $i = n$.
answered Feb 7 at 4:49
Yuval FilmusYuval Filmus
195k14184349
$endgroup$
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: "419"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fcs.stackexchange.com%2fquestions%2f103968%2ffinding-the-maximum-of-a-bitonic-sequence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The first thing that comes to my mind after reading your question is as follow. Draw the sequence as a graph given below. Each $B[i]$ you can think of a point in the graph given below.
The idea to do binary search should be clear from the question as input sequence is almost sorted. Now if you guess the peak point then you are in a good position, but during the binary search if you choose a number which will give you two cases.
The above two cases are the cases in which you need to think, but if you have tried few problems on binary search then now the problem will be easy to solve. More formally you can see the yuval's answer. You ask for the thought process, I have tried to give you my thought process. For any two persons thought process is different, there may be many other way to visualise the problem you have described.
answered Feb 7 at 7:25
aaagaaag
1,142418
$endgroup$
add a comment |
$begingroup$
The first thing that comes to my mind after reading your question is as follow. Draw the sequence as a graph given below. Each $B[i]$ you can think of a point in the graph given below.
The idea to do binary search should be clear from the question as input sequence is almost sorted. Now if you guess the peak point then you are in a good position, but during the binary search if you choose a number which will give you two cases.
The above two cases are the cases in which you need to think, but if you have tried few problems on binary search then now the problem will be easy to solve. More formally you can see the yuval's answer. You ask for the thought process, I have tried to give you my thought process. For any two persons thought process is different, there may be many other way to visualise the problem you have described.
answered Feb 7 at 7:25
aaagaaag
1,142418
$endgroup$
add a comment |
$begingroup$
The first thing that comes to my mind after reading your question is as follow. Draw the sequence as a graph given below. Each $B[i]$ you can think of a point in the graph given below.
The idea to do binary search should be clear from the question as input sequence is almost sorted. Now if you guess the peak point then you are in a good position, but during the binary search if you choose a number which will give you two cases.
The above two cases are the cases in which you need to think, but if you have tried few problems on binary search then now the problem will be easy to solve. More formally you can see the yuval's answer. You ask for the thought process, I have tried to give you my thought process. For any two persons thought process is different, there may be many other way to visualise the problem you have described.
answered Feb 7 at 7:25
aaagaaag
1,142418
$endgroup$
The first thing that comes to my mind after reading your question is as follow. Draw the sequence as a graph given below. Each $B[i]$ you can think of a point in the graph given below.
The idea to do binary search should be clear from the question as input sequence is almost sorted. Now if you guess the peak point then you are in a good position, but during the binary search if you choose a number which will give you two cases.
The above two cases are the cases in which you need to think, but if you have tried few problems on binary search then now the problem will be easy to solve. More formally you can see the yuval's answer. You ask for the thought process, I have tried to give you my thought process. For any two persons thought process is different, there may be many other way to visualise the problem you have described.
answered Feb 7 at 7:25
aaagaaag
1,142418
answered Feb 7 at 7:25
aaagaaag
1,142418
answered Feb 7 at 7:25
aaagaaag
1,142418
answered Feb 7 at 7:25
aaagaaag
1,142418
1,142418
add a comment |
add a comment |
$begingroup$
A sequence satisfying your constraint is known as bitonic. (Strictly speaking, a bitonic sequence is one which is either monotone increasing then decreasing or monotone decreasing then increasing). You can find the index $i^*$ using binary search. The idea is that given an index $i$, you can compare $i$ to $i^*$ as follows:
- If $B[i-1] < B[i] > B[i+1]$, then $i = i^*$.
- If $B[i-1] < B[i] < B[i+1]$, then $i < i^*$.
- If $B[i-1] > B[i] > B[i+1]$, then $i > i^*$.
I'll leave you to handle the corner cases $i = 1$ and $i = n$.
answered Feb 7 at 4:49
Yuval FilmusYuval Filmus
195k14184349
$endgroup$
add a comment |
$begingroup$
A sequence satisfying your constraint is known as bitonic. (Strictly speaking, a bitonic sequence is one which is either monotone increasing then decreasing or monotone decreasing then increasing). You can find the index $i^*$ using binary search. The idea is that given an index $i$, you can compare $i$ to $i^*$ as follows:
- If $B[i-1] < B[i] > B[i+1]$, then $i = i^*$.
- If $B[i-1] < B[i] < B[i+1]$, then $i < i^*$.
- If $B[i-1] > B[i] > B[i+1]$, then $i > i^*$.
I'll leave you to handle the corner cases $i = 1$ and $i = n$.
answered Feb 7 at 4:49
Yuval FilmusYuval Filmus
195k14184349
$endgroup$
add a comment |
$begingroup$
A sequence satisfying your constraint is known as bitonic. (Strictly speaking, a bitonic sequence is one which is either monotone increasing then decreasing or monotone decreasing then increasing). You can find the index $i^*$ using binary search. The idea is that given an index $i$, you can compare $i$ to $i^*$ as follows:
- If $B[i-1] < B[i] > B[i+1]$, then $i = i^*$.
- If $B[i-1] < B[i] < B[i+1]$, then $i < i^*$.
- If $B[i-1] > B[i] > B[i+1]$, then $i > i^*$.
I'll leave you to handle the corner cases $i = 1$ and $i = n$.
answered Feb 7 at 4:49
Yuval FilmusYuval Filmus
195k14184349
$endgroup$
A sequence satisfying your constraint is known as bitonic. (Strictly speaking, a bitonic sequence is one which is either monotone increasing then decreasing or monotone decreasing then increasing). You can find the index $i^*$ using binary search. The idea is that given an index $i$, you can compare $i$ to $i^*$ as follows:
- If $B[i-1] < B[i] > B[i+1]$, then $i = i^*$.
- If $B[i-1] < B[i] < B[i+1]$, then $i < i^*$.
- If $B[i-1] > B[i] > B[i+1]$, then $i > i^*$.
I'll leave you to handle the corner cases $i = 1$ and $i = n$.
answered Feb 7 at 4:49
Yuval FilmusYuval Filmus
195k14184349
answered Feb 7 at 4:49
Yuval FilmusYuval Filmus
195k14184349
answered Feb 7 at 4:49
Yuval FilmusYuval Filmus
195k14184349
answered Feb 7 at 4:49
Yuval FilmusYuval Filmus
195k14184349
195k14184349
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science 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.
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%2fcs.stackexchange.com%2fquestions%2f103968%2ffinding-the-maximum-of-a-bitonic-sequence%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
1
$begingroup$
Has been asked before. Use some sort of binary search.
$endgroup$
– Yuval Filmus
Feb 7 at 3:16
$begingroup$
Could you link me to the question and yes, thanks
$endgroup$
– opp333
Feb 7 at 3:48
$begingroup$
stackoverflow.com/questions/39185197/…
$endgroup$
– Yuval Filmus
Feb 7 at 4:18