Given a (non empty) circularly sorted vector of integers, find the number of times the vector is rotated. Assume that there are no duplicates in the vector and the rotation is in anti-clockwise direction.

For instance, [8, 9, 10, 2, 5, 6] is rotated three times, [9, 10, 2, 5, 6, 8] is rotated two times, [4, 0, 1, 2, 3] is rotated one time, and [2, 5, 8, 9, 12] is rotated zero times.

Solve this problem *iteratively*
in *logarithmic time*, using this C++ header:

int number_of_rotations (const vector<int>& v);

or this Python header:

number_of_rotations(v: list[int]) -> int

Write the invariant of the loop in a comment just before the loop in the function.

Observation You only need to submit the required procedure; your main program will be ignored.

Information

- Author
- Jordi Petit
- Language
- English
- Translator
- Jordi Petit
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Python
- User solutions
- C++ Python