Minimo Array

TAREA : MÍNIMO LOCAL

Un mínimo local de un array A(a-1...b+1) es un elemento A(k) que satisface A(k-1)≥A(k)≤A(k+1). Suponemos que a≤b y A(a-1)≥A(a) y A(b)≤A(b+1);estas
condiciones garantizan la existencia de algún mínimo local. Diseña un algoritmo que encuentre algún mínimo local de A(a-1...b+1) y que sea substancialmente másrápido que el evidente de O(n) en el peor caso.

SOLUCIÓN:
Con la técnica "divide y vencerás":

• Si hay 3 elementos: A(a-1) ≥ A(a) ≤ A(a+1). El mínimo local está en laposición a

• Si hay más de 3 elementos:
Puesto que se pide un algoritmo mejor que lineal, hay que evitar comparar todos los elementos. Si dividimos en dos partesiguales:
• si A((n/2)-1) ≥ A(n/2) ≤ A((n/2)+1) entonces el mínimo local está en la posición n/2
• si no , alguna de las inecuaciones de la condición de arriba no es cierta
•si A((n/2)-1) < A(n/2) entonces nos encontramos en las condiciones que garantizan la existencia de un mínimo local entre (a-1) y (n/2)
• si no entonces nos encontramosen las condiciones que garantizan la existencia de un mínimo local entre ((n/2)-1) y (b+1)

function MIN_LOCAL (A: in Vector) return Indice is
medio: Integer;
beginif A'Length=3 then return(A'First+1);
else medio:= A'Length/2;
if A(medio-1)•A(medio)•A(medio+1)
then return(medio);
elsif A(medio-1)<A(medio)
then returnMIN_LOCAL(A(A'First..medio);
else return MIN_LOCAL(A(medio-1..A'Last);
end if;
end if;
end MIN_LOCAL;

En el caso general del algoritmo se realiza una única llamadarecursiva de tamaño (n/2). Por ello, podemos decir que a MIN_LOCAL le corresponde la función de recurrencia (T(n)= a + T(n/2)) concluyendo por ello que T(n) pertenece a O(lg n).