?
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;
}
