Como ejemplo, examinaremos el método
busquedaLineal
de la clase
ArregloLineal
en la fi gura 16.2. La
invariante para el algoritmo de búsqueda lineal es:
para todas las
k
tales que
0<=k
y
k<indice
datos[ k ] != claveBusqueda
Por ejemplo, suponga que
indice
es igual a 3. Si elegimos cualquier número no negativo menor que 3, como 1
para el valor de
k
, el elemento en
datos
en la ubicación
k
en el arreglo no es igual a
claveBusqueda
. En esencia,
esta invariante establece que la porción del arreglo, llamada
subarreglo
, que abarca desde el inicio del arreglo
hasta, pero sin incluir el elemento en
indice
, no contiene la
claveBusqueda
. Un subarreglo puede contener
cualquier número de elementos.
De acuerdo con el
paso 1, debemos inicializar primero la variable de control
indice
. De la invariante
podemos ver que, si establecemos
indice
en
0
, entonces el subarreglo contiene cero elementos. Por lo tanto,
la invariante es verdadera, ya que un subarreglo sin elementos no puede contener un valor que coincida con la
claveBusqueda
.
El segundo paso es determinar la condición que hace que el ciclo termine. El ciclo debe terminar después
de buscar en todo el arreglo; cuando
indice
es igual a la longitud del arreglo. En este caso, ningún elemento del
arreglo
datos
coincide con la
claveBusqueda
. Una vez que el
indice
llega al fi nal del arreglo, la invariante
sigue siendo verdadera; ningún elemento en el subarreglo (que en este caso es todo el arreglo) es igual a la
clave-
Busqueda
.
Para que el ciclo proceda al siguiente elemento, incrementamos la variable de control
indice
. El último paso
es asegurar que la invariante siga siendo verdadera después de cada iteración. La instrucción
if
(líneas 26 y 27 de
la fi gura 16.2) determina si
datos[ indice ]
es igual a la
claveBusqueda
. De ser así, el método termina y devuelve
indice
. Como
indice
es la primera ocurrencia de
claveBusqueda
en
datos
, la invariante sigue siendo verda-
dera; el subarreglo hasta
indice
no contiene la
claveBusqueda
.
16.5 Conclusión
En este capítulo se presentaron las técnicas de ordenamiento y búsqueda. Hablamos sobre dos algoritmos de
búsqueda (la búsqueda lineal y la búsqueda binaria) y tres algoritmos de ordenamiento (el ordenamiento por
selección, por inserción y por combinación). Presentamos la notación Big O, la cual nos ayuda a analizar la
efi ciencia de un algoritmo. También aprendió acerca de las invariantes de ciclo, que deben seguir siendo verda-
deras antes de que el ciclo empiece a ejecutarse, mientras se está ejecutando y cuando termine su ejecución. En
el siguiente capítulo aprenderá acerca de las estructuras de datos dinámicas, que pueden aumentar o reducir su
tamaño en tiempo de ejecución.
Resumen
Sección 16.1 Introducción
• La búsqueda de datos implica determinar si una clave de búsqueda está presente en los datos y, de ser así, encontrar
su ubicación.
• El ordenamiento implica poner los datos en orden.
Sección 16.2 Algoritmos de búsqueda
• El algoritmo de búsqueda lineal busca cada elemento en el arreglo en forma secuencial, hasta que encuentra el
elemento correcto. Si el elemento no se encuentra en el arreglo, el algoritmo evalúa cada elemento en el arreglo y,
cuando llega al fi nal del mismo, informa al usuario que el elemento no está presente. Si el elemento se encuentra en
el arreglo, la búsqueda lineal evalúa cada elemento hasta encontrar el correcto.
• Una de las principales diferencias entre los algoritmos de búsqueda es la cantidad de esfuerzo que requieren para
poder devolver un resultado.
• Una manera de describir la efi ciencia de un algoritmo es mediante la notación Big O, la cual indica qué tan duro
tiene que trabajar un algoritmo para resolver un problema.
Resumen
709
16_MAQ_CAP_16_DEITEL.indd709
4/19/081:29:40AM