Busqueda De Un Vector

2.1 Introducción
Siendo optimistas, una secretaria podría perder tan sólo uno o dos minutos para encontrar el archivo de uno de los clientes de la compañía para la cual trabaja, esto, asumiendo que los archivos estén perfectamente ordenados y catalogados. Ahora, con una computadora en su oficina, la búsqueda completa puede hacerse en tan sólo unos segundos y la secretaria no tiene que encargarsede volver a buscar el lugar correcto para almacenar el archivo, de eso se encargan los programadores que desarrollan la aplicación de la cual la secretaria toma ventaja. Este es tan sólo un ejemplo de la importancia de las operaciones de búsqueda en un computador, las cuales se realizan a todos los niveles y con infinidad de implementaciones distintas, de la cuales, a continuación presentamosalgunas que son útiles en el caso de que la búsqueda se haga en una estructura de datos lineal.
La búsqueda de un elemento dentro de un array es una de las operaciones más importantes en el procesamiento de la información, y permite la recuperación de datos previamente almacenados. El tipo de búsqueda se puede clasificar como interna o externa, según el lugar en el que esté almacenada la información(en memoria o en dispositivos externos). Todos los algoritmos de búsqueda tienen dos finalidades:
Determinar si el elemento buscado se encuentra en el conjunto en el que se busca.
Si el elemento está en el conjunto, hallar la posición en la que se encuentra.
 
2.2 Búsqueda lineal (secuencial)
Consiste en recorrer y examinar cada uno de los elementos del array hasta encontrar el o los elementosbuscados, o hasta que se han mirado todos los elementos del array.
Este es el método de búsqueda más lento, pero si nuestra información se encuentra completamente desordenada es el único que nos podrá ayudar a encontrar el dato que buscamos. El siguiente algoritmo ilustra un esquema de implementación del algoritmo de búsqueda secuencial:

for(i=j=0;i    if(array[i]==elemento)
   {     solucion[j]=i;
     j++;
   }
Este algoritmo se puede optimizar cuando el array está ordenado, en cuyo caso la condición de salida cambiaría a:

for(i=j=0;array[i]<=elemento;i++)

o cuando sólo interesa conocer la primera ocurrencia del elemento en el array:

for(i=0;i   if(array[i]==elemento)
    break;
En este último caso, cuando sólo interesa la primera posición, se puede utilizar un centinela,esto es, dar a la posición siguiente al último elemento de array el valor del elemento, para estar seguro de que se encuentra el elemento, y no tener que comprobar a cada paso si seguimos buscando dentro de los límites del array:

array[N]=elemento;
for(i=0;;i++)
  if(array[i]==elemento)
    break;
Si al acabar el bucle, i vale N esto indica que no se encontró el elemento. El número medio decomparaciones que hay que hacer antes de encontrar el elemento buscado es de (N+1)/2.
2.2.1. Complejidad de la Búsqueda Lineal.
(A) MEJOR CASO: El algoritmo de búsqueda lineal termina tan pronto como encuentra el elemento buscado en el array. Si tenemos suerte, puede ser que la primera posición examinada contenga el elemento que buscamos, en cuyo caso el algoritmo informará que tuvo éxito después de unasola comparación. Por tanto, la complejidad en este caso será O(1).
(B) PEOR CASO: Sucede cuando encontramos X en la última posición del array. Como se requieren n ejecuciones del bucle mientras, la cantidad de tiempo es proporcional a la longitud del array n, más un cierto tiempo para realizar las instrucciones del bucle mientras y para la llamada al método. Por lo tanto, la cantidad de tiempoes de la forma an + b (instrucciones del mientras * tamaño del arreglo + llamada al método) para ciertas constantes a y b, que representan el coste del bucle mientras y el costo de llamar el método respectivamente. Representando esto en notación O, O(an+b) = O(n).
(C) CASO MEDIO: Supongamos que cada elemento almacenado en el array es igualmente probable de ser buscado. La media puede...

Leer documento completo

Regístrate para leer el documento completo.