```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 ``` ```#include #include using namespace std; int BinarySearch(const vector& r, int from, int to, int x) { int p1 = from; int p2 = to; while (p1 < p2 - 1) { int mid = (p1 + p2 ) / 2; if (x < r[mid]) p2 = mid; else p1 = mid; } if (r[p1] == x) return p1; if (r[p2] == x) return p2; return -1; } int BinarySearchRotatedSortedArray(const vector& r, int x) { int p1 = 0; int p2 = r.size() - 1; while (p1 < p2 - 1) { int mid = (p1 + p2) / 2; if (r[mid] >= r[p1]) p1 = mid; else p2 = mid; } if (r[p1] < r[p2]) p1++; if (x >= r[0]) return BinarySearch(r, 0, p1, x); else return BinarySearch(r, p1 + 1, r.size() - 1, x); } int main() { std::vector x(10); int cur_value = 0; int cur_place = 5; for (int i = 0 ; i < 10; i++) { x[cur_place] = cur_value; cur_value++; cur_place++; cur_place %= 10; } for (int i = 0; i < 10; i++) { cout << x[i] << " "; } cout << endl; for (int i = 0; i < 11; i++) { cout << i << " is at place " << BinarySearchRotatedSortedArray(x, i) << endl; } cout << endl; return 0; } ```
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 ``` ```5 6 7 8 9 0 1 2 3 4 0 is at place 5 1 is at place 6 2 is at place 7 3 is at place 8 4 is at place 9 5 is at place 0 6 is at place 1 7 is at place 2 8 is at place 3 9 is at place 4 10 is at place -1 ```