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, 9

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

SeppJ

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.