StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This can be done in O(1) time best case, O(n) time worst case, and O(lg n) time on average.</p> <p>For a rotated sorted array, if the first element in the array is less than the last element in the array, then the sorted array is not rotated (or rotated 0 position). The minimum element is simply the first element.</p> <p>If the middle element is less than the last element, then the minimum element is in [first, middle].</p> <p>If the middle element is greater than the last element, then the minimum element is in [middle + 1, last].</p> <p>If the middle element is equal to the last element, then there are two sub-cases:</p> <ol> <li>the first element is larger than the last element, in which case the minimum element is in [first, middle + 1];</li> <li>the first element is equal to the last element, in which case it is <em>inconclusive</em> to reject either half of the array. Reduce to linear search. For example, for arrays such as [5,5,5,1,5] and [5,1,5,5,5], it is impossible by just examining the first, last and middle element (since they are all equal) which half of the array the minimum element lies.</li> </ol> <p>I wrote the following code in C++ to solve this problem, which should handle all cases (empty array, repeated elements).</p> <pre><code>template <typename Iterator> Iterator rotated_min(Iterator begin, Iterator end) { while (begin != end) { if (*begin < *(end - 1)) { return begin; } Iterator mid = begin + (end - 1 - begin) / 2; if (*mid < *(end - 1)) { end = mid + 1; } else if (*mid > *(end - 1)) { begin = mid + 1; } else { if (*begin > *(end - 1)) { end = mid + 1; ++begin; } else { //reduce to linear search typename ::std::iterator_traits<Iterator>::value_type min_value = *begin; Iterator min_element = begin; for (Iterator i = begin + 1; i != end; ++i) { if (*i < min_value) { min_value = *i; min_element = i; } } return min_element; } } } return begin; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload