find min in sorted array which is rotated by an unknown number of times
-
hi,
i have an array which is sorted and rotated by an unknown number of times:
22,28,30,1,2,4,10,12,14,20
and i want to find the minimum.i adapted binary search...but not sure if i handle all cases well?
for case 1: im not sure about the search range:
return get_min_in_rotation(vec, l, mid); ...is it mid or mid - 1#include <iostream> #include <vector> #include <numeric> #include <algorithm> using namespace std; // if the elements in the array are rotated by a unknown number of elements we can make the // the following observations: // case 1: arr[r] > arr[mid] -> continue in the left half // e.g. 22,28,30,1,2,4,10,12,14,20 // | | | // l mid r // - the left half is unsorted // - the right half is sorted // -> we keep looking for the min in the left half // // case 2: arr[r] < arr[mid] -> continue in the right half // e.g. 12,14,20,22,28,30,1,2,4,10 // | | | // l mid r // - the left half is sorted // - the right half is unsorted // -> we keep looking for the min in the right half int get_min_in_rotation(vector<int> &vec, int l, int r) { // base case if (vec[l] < vec[r]) return vec[l]; int mid = l + (r - l) / 2; // check for rotation point if(vec[mid+1] < vec[mid]) { return vec[mid+1]; } // case 1: if the most right element is larger than the middle element, the min is in left half else if (vec[r] > vec[mid]) { return get_min_in_rotation(vec, l, mid); // not sure if r = mid or mid - 1???? } // case 2: if the most right element is smaller than the middle element, the min is in right half else if (vec[r] < vec[mid]) { return get_min_in_rotation(vec, mid + 1, r); } } int main() { vector<int> vec = { 3, 4, 5, 1, 2 }; for (int i = 0; i < vec.size(); i++) { for_each(vec.begin(), vec.end(), [](int val) { cout << val << ' '; }); cout << '\n'; cout << "min: " << get_min_in_rotation(vec, 0, vec.size() - 1) << '\n' << endl; rotate(vec.begin(), vec.end() - 1, vec.end()); } return 0; }