Tipos de busqueda en c++

Solo disponible en BuenasTareas
  • Páginas : 7 (1598 palabras )
  • Descarga(s) : 0
  • Publicado : 16 de noviembre de 2011
Leer documento completo
Vista previa del texto
Búsqueda
La recuperación de información, como ya se ha comentado, es una de las aplicaciones mas importantes de las computadoras
La búsqueda (searching) de información esta relacionada con las tablas para consultar (lookup). Esta tablas contienen una cantidad de información que se almacena en forma de lista de parejas de datos. Por ejemplo, un diccionario con una lista de palabras ydefiniciones; un catalogo con una lista de libros de informática; una lista de estudiantes y sus notas; un índice con títulos y contenido de los artículos publicados es una determinada revista, etc. En todos estos casos es necesario con frecuencia buscar un elemento en una lista.
Una vez que se encuentra el elemento, la identificación de su información correspondiente es un problema menor. Porconsiguiente, nos centraremos en el proceso de búsqueda. Supongamos que se desea buscar el vector X [1]..X[n], que tiene componentes numéricos, para ver si contiene o no un numero dado T
Si en vez de tratar sobre vectores se desea buscar información en un archivo, debe realizarse la búsqueda a partir de un determinado campo de información denominado campo clave. Así, en el caso de los archivos deempleados de una empresa, el campo claves puede ser el número de DNI o los apellidos.
La búsqueda por claves para localizar registros es, con frecuencia, una de las acciones que mayor consumo de tiempo conlleva y, por consiguiente, el modo en que los registros están dispuestos y la elección del modo utilizado para la búsqueda pueden redundar en una diferencia sustancial en el rendimiento delprograma.
El programa de búsqueda cae naturalmente dentro de los dos casos típicos ya tratados. Si extienden muchos registros, puede ser necesario almacenarlos en archivos de discos o cinta, externo a la memoria de la computadora. Este caso se denomina búsqueda externa. En el otro caso, los registros que se buscan se almacenan por completo dentro de la memoria de la computadora. Este caso sedenomina búsqueda interna.
En la práctica, en la búsqueda se refiere a la operación de encontrar la posición de un elemento entre un conjunto de elementos dados: lista, tabla o fichero.
Ejemplos típicos de búsqueda son localizar nombre y apellido de un alumno, localizar números de teléfono de una agenda, etc
Existen diferentes algoritmos de busqueda. El algoritmo elegido depende de la forma enque se encuentren organizados los datos.
La operación de busqueda de un elemento N en un conjunto de elementos consiste en:
* Determinan si N pertenece al conjunto y, en caso, indicar su posición en el,
* Determinar si N no perteneces al conjunto

Los métodos mas usuales de búsqueda son:
* Búsqueda secuencial o lineal
* Búsqueda binaria
* Búsqueda por trasformación de claves(hash)
Búsqueda secuencial
Supongamos una lista de elementos almacenados en un vector (arraya unidimensional). El método mas sencillo de buscar un elemento en un vector es explorar secuencialmente el vector o, dicho en otras palabras, recorre el vector desde el primer elemento al ultimo. Si se encuentra el elemento buscado, visualizar un mensaje similar a “fin de búsqueda” ;en caso contrario,visualizar un mensaje similar a ”el elemento no existe en la lista”.
en otras palabras, la busqueda secuencial compara cada elemento del vector con el valor deseado, hasta que este se encuentra o termina de leer el vector completo.
La busqueda secuencial no requiere ningún requisito por parte del vector y, por consiguiente, no necesitaba estar ordenado. El recorrido del vector se realizanormalmente con estructuras respectivas
Ejemplo
Si tiene un vector A que contiene n elementos numéricos (N) >=1(A [1], A[2], A[3], …, A[n]) y se desea buscar un elemento dado t. si el elemento t se encuentra, visualizar un mensaje “el elemento encontrado” y otro que diga “posición=”
Si existe n elementos, se requieran como media n/2 comparaciones para encontrar un determinado elemento. En...
tracking img