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

Anmelden zum Antworten