Problema:
Dato un array di interi ordinato in modo crescente ma ruotato, calcolare il valore minimo.
Input:
Un vettore di interi.
Output:
Un intero che rappresenta il minimo elemento del vettore.
Esempio:
Dato l’array ordinato ruotato:
20, 30, 50, 108, 6, 8, 9, 19
il valore minimo e’ 6
Il mio ragionamento:
Fare una scansione totale dell’array avrebbe complessita’ O(n) e non sfrutterebbe l’informazione aggiuntiva che l’array e’ ordinato e ruotato.
Si puo’ allora pensare di fare una specie di ricerca binaria con complessita’ O(log(n)) guidata dal valore dell’elemento centrale dell’array e dell’elemento finale.
Se l’elemento finale e’ maggiore o uguale all’elemento centrale allora il minimo si trova nella prima meta’ dell’array altrimenti nell’altra. Nota che l’elemento centrale potrebbe essere il minimo solamente nel primo caso (questo motiva l’utilizzo di m invece che m-1 nel codice seguente).
La mia soluzione:
private static int InternalMin(int[] v, int a, int b)
{
if (a == b) return v[a];
int m = (a + b) / 2;
return (v[b] >= v[m]) ? InternalMin(v, a, m) : InternalMin(v, m + 1, b);
}
public static int Min(int[] v)
{
if (v == null) throw new ArgumentNullException("v");
if (v.Length == 0) throw new ArgumentException("v must contain at least one element");
return InternalMin(v, 0, v.Length - 1);
}