BÚSQUEDA
SECUENCIAL
Y BINARIA
Integrantes :
-BELINDA BARRIENTOS
-LUZ QUISPE
-PERCY MAMANI
-LUIS APAZA RAMIREZ
-MIGUEL OSCCO
Procesos de 1
Búsqueda Los procesos de búsqueda
involucran recorrer un arreglo
completo con el fin de encontrar
algo. Lo más común es buscar
el menor o mayor elemento
(cuando es puede establecer un
orden), o buscar el índice de un
Para encontrar un dato dentro de un arreglo, para
ello existen diversos algoritmos que varían en elemento determinado.
complejidad, eficiencia, tamaño del dominio de
búsqueda
1
Se le conoce como búsqueda lineal.
2 Este método consiste en recorrer el arreglo o
Búsqueda
vector elemento a elemento e ir comparando
con el valor buscado (clave)
secuencial.
3
Se empieza con la primera casilla del vector y
se observa una casilla tras otra hasta que se
encuentre el elemento buscado
4
El resultado de la búsqueda es un solo valor, y
será la posición del elemento buscado o cero
5 funciona bien con arreglos pequeños o para
arreglos no ordenados.
BUSQUEDA SECUENCIAL 4
VENTAJAS
• Es un método sumamente simple que resulta útil DESVENTAJAS
cuando se tiene un conjunto de datos pequeños • Este método tiende hacer muy lento.
(Hasta aproximadamente 500 elementos)
• Si los valores de la clave no son únicos, para
• Es fácil adaptar la búsqueda secuencial para que encontrar todos los elementos con una clave
utilice una lista enlazada ordenada, lo que hace la particular, se requiere buscar en todo el arreglo,
búsqueda más eficaz. lo que hace el proceso muy largo.
• Si los datos buscados no están en orden es el
único método que puede emplearse para hacer
dichas búsquedas.
5
Búsqueda
1
Binaria 2 Una búsqueda más eficiente puede
hacerse sobre un arreglo ordenado.
3
La Búsqueda Binaria, compara si
4 el valor buscado está en la mitad
superior o inferior. En la que esté,
5 subdivido nuevamente, y así
sucesivamente hasta encontrar el
6 valor.
7
En 1946, John Mauchly mencionó por
I A: primera vez la búsqueda binaria como
parte de Moore School Lectures, el primer
O R conjunto de conferencias relacionado con
I ST las computadoras. Las siguientes
publicaciones mencionaban que la
H búsqueda binaria solo funcionaba en
arreglos cuya longitud fuese de uno
menos que una potencia de dos hasta
1960, cuando Derrick Henry Lehmer
público un algoritmo de búsqueda binaria
que funcionaba en todos los arreglos
ordenados.
8
Supóngase un vector v de 20 elementos ordenado de forma ascendente, como se muestra en la figura, en el que se
busca el número 10. (clave = 10).
La primera iteración toma como espacio de búsqueda el vector completo y se ubica en el elemento de la mitad.
Para determinar cuál es elemento de la mitad se suma el índice del extremo inferior con el índice del extremo
superior del espacio de búsqueda y se divide para dos.
(1 + 13) / 2 = 7
Se averigua si la clave está en el elemento del centro:
clave = v[7]?
10 = 14?
9
Búsqueda Binaria. 10
VENTAJAS DESVENTAJAS
Se puede aplicar tanto a Este método funciona
datos en listas lineales como solamente con arreglos
en árboles binarios de ordenados, por lo cual si
búsqueda. nos encontramos con
Es el método más eficiente arreglos que no están en
para encontrar elementos en orden, este método, no nos
un arreglo ordenado. ayudaría en nada.
11
DIFERENCI En el caso del método de búsqueda binaria, los 12
arreglos deben estar únicamente ordenados, como
A ENTRE se planteo anteriormente, por su parte el método
de búsqueda secuencial o lineal, puede emplearse
AMBOS tanto en arreglos pequeños, como en aquellos que
no están ordenados.
METODOS En segundo orden, podemos ver que el método de
búsqueda binaria, es el método más eficiente para
encontrar elementos en un arreglo ordenado, lo
contrario sucede con el método de búsqueda
secuencial ya que este es muy lento, pero si los
datos no están en orden es el único método que
puede emplearse para hacer las búsquedas.
