Timeline for Is there a O(log n)-time algorithm to find the maximum element of a circular shift of a sorted array?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 3, 2019 at 11:23 | answer | added | Fazal Ur Rehman Fazal | timeline score: 0 | |
| Nov 3, 2019 at 7:31 | comment | added | D.W.♦ | What did you try? Where did you get stuck? Can you recognize any of the four cases? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. | |
| Nov 2, 2019 at 14:59 | vote | accept | user3760100 | ||
| Nov 2, 2019 at 10:42 | answer | added | Steven | timeline score: 4 | |
| Nov 2, 2019 at 10:36 | comment | added | gnasher729 | Let N>= 3 be the array size, n = N/3, m=2N/3, x=position of last element. Read a, b, c from index 0, n and m. a, b, c can be sorted in six different ways, and each corresponds to one of the six cases array sorted in ascending/descending order, and x<n, n<=x<m, and x>= m. The rest is binary search in a sub array of size N/3, so O(log N). | |
| Nov 2, 2019 at 10:26 | history | reopened |
gnasher729 Discrete lizard♦ |
||
| Nov 2, 2019 at 5:15 | review | Reopen votes | |||
| Nov 2, 2019 at 10:26 | |||||
| S Nov 2, 2019 at 4:55 | history | suggested | Steven | CC BY-SA 4.0 |
Added problem description, changed the titled to be more informative. Rephrased the question to clarify OP is referring to time complexity.
|
| Nov 2, 2019 at 4:20 | comment | added | Evil | @Steven yes, and edit was very good. | |
| Nov 1, 2019 at 21:46 | review | Suggested edits | |||
| S Nov 2, 2019 at 4:55 | |||||
| Nov 1, 2019 at 18:31 | comment | added | Steven | The question has been put on hold seconds before I could post my answer. Am I allowed to edit the question even if I'm not the original poster? | |
| Nov 1, 2019 at 18:23 | history | closed |
ryan D.W.♦ |
Needs details or clarity | |
| Nov 1, 2019 at 17:45 | review | Close votes | |||
| S Nov 1, 2019 at 18:25 | |||||
| Nov 1, 2019 at 16:45 | comment | added | Yuval Filmus | Please include the question as part of your post. The link could rot in the future. | |
| Nov 1, 2019 at 16:45 | review | First posts | |||
| S Nov 1, 2019 at 18:25 | |||||
| Nov 1, 2019 at 16:44 | history | asked | user3760100 | CC BY-SA 4.0 |