Rightmost position of insertion

Write an efficient function

    int rightmost(double x, const vector<double>& v);

that returns the rightmost position where $x$ could be inserted in the sorted vector $v$ (by adding one position at the end of $v$ and moving the necessary elements one position to the right) so that $v$ would remain sorted.

For instance, assume that $x$ is 23. If $v$ is $[15, 15, 20, 30, 40, 40]$ , then we must insert $x$ at the position 3 (between 20 and 30), and the resulting $v$ would be $[15, 15, 20, 23, 30, 40, 40]$ . If $v$ is $[17, 23, 23, 35, 42, 42]$ , then we could insert $x$ at the positions 1, 2 or 3, so your function must return 3. If $v$ is $[3, 5, 7, 9]$ , $x$ should be inserted at the position just to the right of the end of the vector, that is, 4. As a final example, if $v$ is $[23, 23]$ , $x$ should be inserted at 2.

Precondition

The vector $v$ is sorted in nondecreasing order.

Observations

Your solution can only include the vector library.
You can write and use additional functions if you need them.
You only need to submit the required procedure; your main program will be ignored.

Problem information

Author: Unknown
Translator: Salvador Roura

Generation: 2026-03-10T20:03:56.512Z