Nose
Páginas: 26 (6354 palabras)
Publicado: 7 de noviembre de 2010
Este problema puede reducirse a devolver laexistencia de un número en un vector.
Búsqueda secuencial [editar]
Se utiliza cuando el contenido del vector no se encuentra o no puede ser ordenado. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta que éste se encuentre, o hasta que se llegue al final del arreglo. La existencia se puede asegurar desde el momento que el elemento eslocalizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo. A continuación se muestra el pseudocódigo del algoritmo:
Datos de Entrada:
vec: vector en el que se desea buscar el elemento
tam: tamaño del vector
dato: elemento que se quiere buscar.Variables
pos: posición actual en el arreglo
pos = 0
Mientras pos < tam:
Si vec[pos]== dato devolver verdadero y/o pos, de lo contrario:
pos = pos + 1
Fin (Mientras)
Devolver falso
Búsqueda binaria (dicotómica) [editar]
Se utilizacuando el vector en el que queremos determinar la existencia o no de un elemento está ordenado, o puede estarlo, este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente con el número de iteraciones.
Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del arreglo (normalmente el elemento central), si el valor de éstees mayor que el del elemento buscado se repite el procedimiento en la parte del arreglo que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del arreglo que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible, con el elemento buscado como elemento central. Si elelemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en el arreglo.
A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central del arreglo.
Datos de Entrada:
vec: vector en el que se desea buscar el elemento
tam: tamaño del vectordato: elemento que se quiere buscar.
Variables
centro: elemento central del intervalo
inf: limite inferior del intervalo
sup: limite superior del intervalo
inf = 0
sup = tam-1
Mientras inf <= sup:centro = ((sup + inf) / 2) /* división entera: se trunca la parte decimal */
Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario:
Si dato < vec[centro] entonces:
sup=centro-1
En caso contrario:
inf=centro+1
Fin (Mientras)Devolver Falso
Metodos de Busquedas
Busqueda Secuencial
Definicion:
La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave.
Búsqueda secuencial, también se le conoce...
Leer documento completo
Regístrate para leer el documento completo.