Investigación búsqueda
TECNOLOGÍAS DE LA INFORMACIÓN, ÁREA
DESARROLLO DE SOFTWARE MULTIPLATAFORMA
Presenta:
Marcos Eduardo Camacho Viay
Docente:
ING. Marcos Antonio Azcona Ramírez
Jalpan de Serra, Qro. 20 de septiembre del 2023
Índice
Búsqueda lineal .................................................................................. 3
Búsqueda binaria ................................................................................ 3
Función búsqueda............................................................................... 4
Búsqueda lineal
La búsqueda lineal o secuencial es la técnica más simple para buscar un elemento en un array
(vector). Consiste el método en el recorrido de todo el vector, desde el primer elemento hasta el
último, y de uno en uno. Si el vector contiene el elemento, el proceso devolverá la posición del
elemento buscado dentro del vector y, en caso contrario, un mensaje que indique la falta de éxito
en la búsqueda.
Mediante un bucle desde se compara el elemento t buscado con a[i]. En caso de encontrarlo, se
almacena la posición (el índice del array) del mismo y finalmente se devolverá al programa
principal. Dado que los algoritmos de búsqueda normalmente sólo devuelven la posición, es muy
frecuente que la implementación del algoritmo se haga con una función.
Eficiencia de la búsqueda lineal
El método de búsqueda secuencial, en el peor de los casos (el elemento buscado está al final de la
lista o no existe). requiere consultar los n elemento de la lista para encontrar el elemento deseado
o determinar que el elemento no existe en la lista. Entonces el tiempo de búsqueda es
directamente proporcional al número de elementos de la listo, por loque utilizando la notación O
se tiene para el tiempo t la formula
𝑡 = 𝑂[𝐹(𝑁)]
Búsqueda binaria
la búsqueda binaria es el método idóneo, Se basa en el conocido método de divide y vencerás.
Este método tiene una clara expresión en la búsqueda de una palabra en un diccionario. Cuando
se busca una palabra no se comienza la búsqueda por la página I y se sigue secuencialmente, sino
que se abre el diccionario por una página donde te se piensa puede estar la palabra, es decir, se
divide el diccionario en dos partes; abrir la página se ve si se ha acertado o en qué parte (la
primera o la segunda) se encuentra la palabra buscada. Se repite este proceso hasta que por
divisiones o aproximaciones sucesivas se encuentra la palabra,
Se examina en primer lugar el elemento central de la lista (las divisiones se toman
iguales), 1898. Dado que 1989 es mayor que 1898, el elemento a buscar estará en
segunda mitad:
EI elemento central en esta sublista es 2400, y como 1989 es menor, la nueva
donde buscar es
La búsqueda binaria requiere una ordenación previa del vector o lista en el que se va a efectuar la
búsqueda. Por consiguiente, las acciones típicas (módulos) en un algoritmo de búsqueda binaria
son:
• Lectura del vector,
• Ordenación del vector.
• Búsqueda binaria,
• Visualizar resultados,
En el algoritmo de búsqueda binaria, con cada comparación se divide en dos mitades el
tamaño de la lista en estudio. Si n es el tamaño de la lista, los tamaños sucesivos de sublistas serán
𝑛 𝑛 𝑛
2´ 4´ 8´
𝑛 𝑛 𝑛
21 22 23
Función búsqueda
Datos de entrada:
Array ordenado A primero, ultimo (índices extremos de A) clave (elementos buscados)
Datos de salida:
Verdadero, falso (existe/no existe la clave buscada
Mezcla
El proceso de mezcla, fusión o intercalación (merge en ingles) consiste en tomar dos vectores
ordenados (a,b) y obtener un nuevo vector © también ordenado El algoritmo mas sencillo para
resolver el problema es:
• Situar todos los elementos del vector a en cl nuevo vector c.
• Situar todos los elementos del vector b en eI nuevo vector c.
• Ordenar todo el vector c.
