min suche, im sortierten array
-
Hi,
ich moechte das min element in einem sortieren + rotierten array finden... e.g.
10, 12, 14, 1, 3, 5, 8, 9warum muss ich fuer folgenden case die grenzen: (l, mid) nehmen und nicht (l, mid - 1) ?
das array hat keine duplicates...
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]; } // 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); } // 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 = { 10, 12, 14, 1, 3, 5, 8, 9}; cout << get_min_in_rotation(vec, 0, vec.size() - 1) << endl; }
-
Was für eine Antwort erwartest du? Weil du mit der Abfrage in Zeile 12 noch nicht ausgeschlossen hast, dass das mid-Element das kleinste im ganzen Array sein kann. Dieses muss daher im nächsten Rekursionsschritt mit betrachtet werden.