transparencias leccion17

Algorítmica y Lenguajes de Programación
Búsqueda

Búsqueda. Introducción
n

Hace dos lecciones se dijo que había tres tratamientos básicos sobre
vectores:
n
n
n

n

n

n

n

n

Recorrido.
Ordenación.
Búsqueda.

Durante las últimas clases hemos estudiado distintos métodos de
ordenación de vectores; pudiendo adaptarse dichos métodos a otras
estructuras de datos.
En la lección de hoy se estudiarándistintos algoritmos de
búsqueda.
Los algoritmos de búsqueda tienen como finalidad localizar un elemento
dado dentro de una estructura de datos o determinar su inexistencia.
Naturalmente, la búsqueda será mucho más eficiente si la estructura de
datos (en nuestro caso el vector) está ordenada.
Así, los algoritmos que estudiaremos servirán para realizar búsquedas en
vectores ordenados.
2

1Búsqueda. Algoritmos de búsqueda
n

A lo largo de esta lección estudiaremos los
siguientes algoritmos de búsqueda:
n
n
n
n

n

Búsqueda
Búsqueda
Búsqueda
Búsqueda

secuencial.
secuencial con centinela.
binaria (o dicotómica)
por interpolación.

Como en el caso de los métodos de
ordenación, se presentará pseudocódigo,
código FORTRAN y análisis de la complejidad
para cada uno de los algoritmos.
3

Búsqueda.Búsqueda secuencial (i)
n

n

n

El algoritmo de búsqueda más sencillo recorre
el vector desde el primer elemento hasta el
último y si encuentra el valor buscado retorna
su posición.
Obviamente, se trata del único algoritmo
posible si el vector no está ordenado.
Sin embargo, si el vector está ordenado
resulta muy ineficiente.
4

2

Búsqueda. Búsqueda secuencial (ii)
entero funciónbusquedaSecuencial (v ∈ vector(MAX) de elemento, valor
∈ elemento)
variables
i, posicion ∈ entero
posicionß
ß -1
desde iß
ß 1 hasta MAX
si v(i)=valor entonces
posicionß
ßi
fin si
fin desde
busquedaSecuencialß
ß posicion
fin funcion
5

Búsqueda. Búsqueda secuencial (iii)
integer function busquedaSecuencial (vector,valor)
implicit none
integer vector(max)
integer valor
integer i,posicion
posicion=-1
do i=1,max
if(vector(i)==valor) then
posicion=i
end if
end do
busquedaSecuencial=posicion
end function
6

3

Búsqueda. Búsqueda secuencial (iv)
n

n

n

n

n

Como se puede apreciar el algoritmo realiza siempre el
mismo número de iteraciones independientemente de
la posición en que se encuentre el valor buscado.
El número de iteraciones siempre es igual al tamaño del
vector y, puesto que todas lasoperaciones del interior del
bucle tienen coste unitario, la complejidad del algoritmo
de búsqueda secuencial es O(n).
El algoritmo de búsqueda secuencial resulta muy ineficiente
puesto que no se aprovecha del hecho de que el vector esté
ordenado.
Es posible modificarlo para que, teniendo en cuenta esa
circunstancia, finalice en cuanto localice el elemento o
se determine que éste no existe.
Estamodificación se conoce como búsqueda
secuencial con centinela.
7

Búsqueda. Búsqueda secuencial con
centinela (i)
n

n

n

Si el vector está ordenado no es necesario
recorrerlo completamente.
En cuanto el valor buscado es encontrado se
puede finalizar el recorrido y en el momento
en que aparece un valor mayor que el
buscado también se puede detener la
ejecución.
Al aplicar esto al algoritmo de búsquedasecuencial se obtiene el algoritmo de
búsqueda con centinela.
8

4

Búsqueda. Búsqueda secuencial con
centinela (ii)
entero funcion busquedaSecuencialCentinela (v ∈ vector(MAX) de elemento, valor
∈ elemento)
variables
i ∈ entero
iß
ß1
mientras v(i) iß
ß i+1
fin mientras
si v(i)=valor entonces
busquedaSecuencialCentinelaß
ßi
si no
busquedaSecuencialCentinelaß
ß -1
fin si
fin funcion9

Búsqueda. Búsqueda secuencial con
centinela (iii)
integer function busquedaSecuencialCentinela (vector,valor)
implicit none
integer vector(max)
integer valor
integer i
i=1
do while ((vector(i) i=i+1
end do
if (vector(i)==valor) then
busquedaSecuencialCentinela=i
else
busquedaSecuencialCentinela=-1
end if
end function
10

5

Búsqueda. Búsqueda secuencial con
centinela...

Leer documento completo

Regístrate para leer el documento completo.