Algoritmo de Busqueda

Departamento de Informática
Universidad de Valladolid
Campus de Segovia
______________________

TEMA 6:
ALGORITMOS DE
BÚSQUEDA Y
ORDENACIÓN

Prof. José Vicente Álvarez Bravo

ALGORITMOS DE BÚSQUEDA
Y ORDENACIÓN
• Algoritmos de búsqueda en arrays
– Secuencial
– Secuencial ordenada
– Binaria

• Ordenación de vectores
– Selección directa
– Inserción directa
– Intercambiodirecto
– Ordenación rápida (Quick Sort)
– Ordenación por mezcla (Merge Sort)

• Algoritmos de búsqueda y ordenación en
archivos

ALGORITMOS DE BÚSQUEDA
EN ARRAYS
• Surgen de la necesidad de conocer tanto si
un dato se encuentra o no dentro de una
colección como de la posición que ocupa.

• Búsqueda(vector,elemento):
– i∈{1,....,n} si existe tal elemento
– 0
en otro caso

•Estructura de datos:
const
N=100;
type
tIntervalo=0..N;
tvector=array[1..N] of tElem {tipo ordinal}

ALGORITMOS DE BÚSQUEDA
EN ARRAYS

• Algoritmos de búsqueda:
– Búsqueda secuencial
– Búsqueda secuencial ordenada
– Búsqueda binaria

BÚSQUEDA SECUENCIAL
• La búsqueda secuencial consiste en
comparar secuencialmente el elemento
deseado con los valores contenidos en las
posiciones1,....,n.
• El proceso termina cuando o bien
encontramos el elemento o bien se alcanza
el final del vector.
• Un primer nivel de diseño:
ind:=0
buscar elemento en vector
si vector[ind]=elemento entonces
busquedasecuencial:=ind
sino
busquedasecuencial:=0

BÚSQUEDA SECUENCIAL,
IMPLEMENTACIÓN EN PASCAL

FUNCTION Busquedasec(v:tvector ; elem:telem):tIntervalo;
{Dev. 0 si el elemento no estáen ‘v’ o i si v[ì]=elem}
VAR
i:tIntervalo;
BEGIN
i:=0;
repeat
i:=i+1;
until (v[i]=elem) or (i=N);
if v[i]=elem then
busquedasec:=i
else
busquedasec:=0
END; {busquedasec}

Este algoritmo en el peor de los casos es de orden O(n).

BÚSQUEDA SECUENCIAL
ORDENADA

• El algoritmo anterior puede ser mejorado si
el vector ‘v’ esta ordenado (i.e. Creciente).
• De esta forma si durantela búsqueda se
alcanza una componente con mayor valor
que ‘elem’, podremos asegurar que no se
encuentra dentro de la colección.

BÚSQUEDA SECUENCIAL
ORDENADA,
IMPLEMENTACIÓN EN PASCAL
FUNCTION Busquedasecord(v:tvector ; elem:telem):tIntervalo;
{Dev. 0 si el elemento no está en ‘v’ o i si v[ì]=elem}
VAR
i:tIntervalo;
BEGIN
i:=0;
repeat
i:=i+1;
until (v[i]≥elem) or (i=N);
ifv[i]=elem then
busquedasecord:=i
else
busquedasecord:=0
END; {Busquedasecord}

Este algoritmo en el peor de los casos es de orden O(n).

BÚSQUEDA BINARIA
• El hecho de que el vector este ordenado se
puede, también, aprovechar para conseguir
una mayor eficiencia planteando el
siguiente algoritmo.
– Comparar ‘elem’ con el elemento central del
vector. Si este es el elemento buscado sefinaliza. Si no se sigue buscando en la mitad del
vector que determine la relación entre el valor
del elemento central y el buscado.
– Este algoritmo finaliza cuando se localiza el
elemento o se termina el vector.

• Debido a que el vector es dividido
sucesivamente en dos se denomina
búsqueda binaria.

BÚSQUEDA BINARIA,
IMPLEMENTACIÓN EN PASCAL
FUNCTION Busquedabinaria(v:tvector ;elem:telem):tIntervalo;
{Prec. V esta ordenado crecientemente}
{Dev. 0 si el elemento no está en ‘v’ o i si v[ì]=elem}
VAR
einf,esup,posmed:tIntervalo;
encontrado:boolean;
BEGIN
einf:=1; esup:=N; encontrado:=false;
while not encontrado and (esup≥einf) do begin
posmed:=(esup+einf) DIV 2;
if elem=v[posmed] then
encontrado:=true
else if elem>v[posmed] then
einf:=postmed+1
else
esup:=postmed-1end {while}
if encontrado then
busquedabinaria:=posmed
else
busquedabinaria:=0
END; {Busquedabinaria}

BÚSQUEDA BINARIA
• La complejidad algorítmica de la búsqueda
binaria es:
Si
2k≤ N≤2k+1
entonces:
T(n) ≤T(2k+1)
En el peor de los casos:
T(n)≈O[logN]
N ≤ 2k+1=22k
logN ≤ log2k+1=k+1

ORDENACIÓN DE VECTORES
• Como se ha presentado con anterioridad,
disponer de una...