Bienvenidos a este nuevo capítulo de este Curso Gratis de Programación #19 Algoritmos de Búsqueda
¿Te gustaría enterarte de cuando lanzamos descuentos y nuevos cursos?
Búsqueda. Métodos.
Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento concreto dentro de una estructura de datos. Consiste en solucionar un problema de existencia o no de un elemento determinado en un conjunto finito de elementos, es decir, si el elemento en cuestión pertenece o no a dicho conjunto, además de su localización dentro de éste.
Búsqueda binaria:
La búsqueda secuencial puede resultar muy lenta si el número de elementos del conjunto es grande. El algoritmo de búsqueda binaria reduce considerablemente los tiempos de búsqueda, pero es requisito para aplicar este algoritmo que los elementos del conjunto se encuentren ordenados. Este algoritmo utiliza la técnica de “divide y vencerás”. Se compara si el elemento central del conjunto ordenado es el valor que se busca.
En el caso de que lo sea, se finaliza la búsqueda; en caso contrario, se debe verificar si el valor que buscar es más chico que el valor central para continuar trabajando con la primera mitad de valores del conjunto. Si el valor que buscar es más grande que el elemento central, entonces se debe continuar trabajando con la segunda mitad de valores del conjunto.
Con la sub lista de elementos, se debe repetir el proceso de comparación del valor que buscar con el elemento central, pero en este caso de la sublista. Si el elemento central de la sublista no es el valor que se busca, se prosigue con la subdivisión del conjunto hasta determinar la existencia, o no, del valor. En un arreglo unidimensional X ordenado, de N elementos, si se desea buscar el valor K, el pseudocódigo de búsqueda binaria es el siguiente:
leer(K)
BAJO <- 1
ALTO <-N
CENTRAL <-(BAJO+ALTO) div2
mientras (BAJO <=AL TO) Y ( X[CETRAL]<> K ) hacer
si K < X[CENTRAL] entonces
ALTO <-CENTRAL - 1
si-no
BAJO <-CENTRAL + 1
fin -si
CENTRAL <- (BAJO + ALTO) div 2
fin-mientras
si K == X[CENTRAL] entonces
escribir("Valor encontrado en la posición ", CENTRAL)
fin-si Ejemplo de búsqueda binaria
Arreglo inicial:
En este escenario el valor que buscar es 8
En este escenario el valor que buscar es 11
Arreglo inicial:
El método de búsqueda binaria requiere que el conjunto de elementos se encuentre ordenado, pero la cantidad de comparaciones necesarias para buscar un elemento se reduce considerablemente. Para un arreglo de N elementos, en el peor de los casos, se necesitarán log2(N+ 1) comparaciones y, en el mejor de los casos, se realizará una comparación. El método de búsqueda binaria necesita realizar, en promedio, la siguiente cantidad de comparaciones para encontrar un elemento:
Este tipo de búsqueda es usado en listas que estén previamente ordenadas, ya que su método de búsqueda es la de dividir los datos en dos grupos, eligiendo el grupo en el cual debería estar el dato buscado (supone que está ordenado alfabéticamente o numericamente), volviendo a aplicar la división, y así sucesivamente hasta verificar si existe o no existe el dato buscado.
Solución del Problema con la Búsqueda Binaria:
Problema de la Búsqueda: Dada una lista xn y un valor x devolver el índice de x en xn si x está en xn, y −1 si x no está en xn.
Procedimiento: Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del vector (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del vector que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del vector 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. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el vector.
Ejemplo
#Este es el vector que el algoritmo usara para buscar cualquier dato
vector = [3, 5, 8, 9, 10, 22, 45, 500, 900, 4253]
#La variable puntero sera el inicio del vector, que es 0
puntero = 0
#vectorLen contiene la longitud del vector
vectorLen = len(vector)
#La varieable encontrado cambiara su valor, y asi el algoritmo sabre que hacer
encontrado = False
#Le pedimos al usuario una entrada de un entero
numero = int(input(«Ingresar el dato que desea buscar: «))
#Creamos un bucle que no se detenga hasta que encontrado sea diferente de False
#Y que puntero sea menor o igual que vectorLen
while not(encontrado) and puntero <= vectorLen:
#Creamos la variable mitad
mitad = int((puntero+vectorLen) / 2)
#Si numero es igual que el indice mitad en vector
if numero == vector[mitad]:
#Encontado sera igual a True
encontrado = True
elif numero < vector[mitad]:
#vectorLen sera igual que mitad – 1
vectorLen = mitad – 1
#De lo contrario
else:
#Puntero sera igual que mitad + 1
puntero = mitad + 1
#Si encontrado es True
if(encontrado):
#Mostramos un mensaje con la posicion del Dato en el vector
print(«El dato se encuentra en la posición «, str(mitad+1))
#Mostramos el vector ordenado
print(vector)
#De lo contrario
else:
#Mostramos un mensaje
print(«El dato no se encontró»)
Resultado:
Ingresar el dato que desea buscar: 8
El dato se encuentra en la posición 3
[3, 5, 8, 9, 10, 22, 45, 500, 900, 4253]
¡Excelente! hemos cumplido con nuestro objetivo, resolvimos el problema de la búsqueda con 2 algoritmos diferentes, como pueden ver, los algoritmos de búsqueda aparte de ser muy interesantes son de mucha ayuda, espero que te haya sido de utilidad, ya sea para resolver problemas o para reforzar tus conocimientos.
Ejercicio 1
Algoritmo integrador de ordenamiento y búsqueda. El algoritmo crea un vector y despliega por pantalla un menú de opciones para ordenar y buscar algún elemento del arreglo.
Algoritmo Ordenamiento
Definir N, opcionlngresada, i, j, cantidadComparaciones, AUX, k, cantidadOperacionesBusqueda, ALTO, BAJO, CENTRAL
Como Entero
Definir sw, encontrado Como Lógico
Escribir "Algoritmo de ordenamiento y búsqueda"
Escribir "Ingrese la cantidad de elementos con los que va trabajar"
Leer N
Dimension X(N)
Repetir
Escribir ""
Escribir "Menú de operaciones"
Escribir "1. Generar vector aleatorio"
Escribir "2. Mostrar vector"
Escribir "3. Ordenar vector por método de burbuja"
Escribir "4. Ordenar vector por método de burbuja mejorada"
Escribir "5. Ordenar vector por método de inserción"
Escribir "6. Ordenar vector por método de selección"
Escribir " 7. Buscar un elemento (búsqueda secuencial)"
Escribir "8. Buscar un elemento (búsqueda binaria)"
Escribir "0. Salir"
Escribir Sin Saltar "-- Ingrese una opción"
Leer opcionlngresada
Escribir ""
Segun opcionlngresada Hacer
1:
Escribir "Generación aleatoria del vector "
Para <-1 hasta 20 hacer
x[i]<-azar(100)
FÍnPara
2:
Escribir " Mostrando elementos del vector "
Para i<-1 hasta N hacer
Escribir Sin Saltar X[i], " "
FinPara
Escribir " "
3:
Escribir "Ordenamiento por método de burbuja"
Cantidadcomparaciones <-0
Para i<-1 hasta N-1 hacer
Para j<-1 hasta N-1 hacer
Si X[j] > X[j+1] entonces
AUX<-Z[j]
X[j]<-X[j+1]
X[j+1]<-AUX
FinSi
cantidadcomparaciones<-cantidadComparaciones+1
FinPara
Finpara
Escribir "Cantidad de comparaciones realizadas: ",cantidadcomparaciones
4:
Escribir "Ordenamiento por método burbuja mejorada"
cantidadComparaciones <-0
para i<-1 hasta N-1 hacer
para j<-1 hasta N-1 hacer
Si X[j] >X[j+1] entonces
AUX<-x[j]
X[j]<-X[j+1]
X[j+1]<-AUX
FinSi
cantidadcomparaciones<-cantidadComparaciones+1
Finpara
Finpara
Escribir "Cantidad de comparaciones realizadas: ",cantidadcomparaciones
5:
Escribir "Ordenamiento por método de inserción"
Para i<-2 hasta N hacer
AUX <-X[i]
K <-i-1
sw <- Falso
Mientras NO(sw) y (k>= 1) hacer
Si AUX X[k] entonces
X[k+1l<- X[k]
k<-k-1
SiNo
sw <-Verdadero
FinSi
FinMientras
X[k+1] <- AUX
FinPara
6:
Escribir "Ordenamiento por método de selección"
cantidadComparaciones <-O
Para i<-1 hasta N-1 hacer
AUX <-x[i]
k<-i
Para j<-i+1 hasta N hacer
Si x[j] < AUX entonces
AUX<-x[j]
k<-j
FinSi
cantidadcomparaciones< -canparaciones+1
Fin Para
X[k]<-x[i]
X[i]<- AUX
FinPara
Escribir "Cantidad de comparaciones realizadas: ",cantidadcomparaciones
7:
Escribir "Búsqueda secuencial de un elemento"
Escribir Sin Saltar "Ingrese el elemento que desea buscar"
Leer K
encontrado <-Falso
Para <-1 hasta N hacer
Si X[i] = K entonces
Escribir "Se ha encontrado el elemento en la posición ", i
encontrado <-Verdadero
FinSi
FinPara
Si encontrado = Falso entonces
Escribir "No se ha encontrado el elemento"
FinSi
8:
Escribir "Búsqueda binaria de un elemento "
Escribir Sin Saltar "Ingrese el elemento que desea buscar"
Leer K
cantidadOperacionesBusqueda <-0
BAJO<- 1
ALTO <-N
CENTRAL <-redon((BAJO + AL TO) / 2)
Mientras (BAJO <=AL TO) Y (X[CENTRAL] <>K) hacer
Si K < X[CENTRAL] entonces
ALTO <-CENTRAL -1
SiNo
BAJO <-CENTRAL +1
Fin Si
CENTRAL <- redon((BAJO + ALTO) / 2)
cantidadOperacionesBusqueda <- cantidadOperacionesBusqueda + 1
FinMientras
Si k=X[CENTRAL] Entonces
Escribir "Se ha encontrado el elemento en la posición ", CENTRAL
SÍNO
Escribir "No se ha encontrado el elemento"
FinSi
Escribir "Cantidad de operaciones de búsqueda realizadas: cantidadOperacionesBusqueda
0:
Escribir " Gracias por utilizar el programa. Hasta luego! "
De Otro Modo:
Escribir " Opción ingresada incorrecta "
Fin Segun
Hasta Que opcionlngresada = 0
FinAIgoritmo Ejercicio 2
Las estructuras tipo Arreglo se utilizar para facilitar EL MANERO DE LOS DATOS DENTRO DE UN OPROGRAMA A DIFERENCIA DE LA DELARACION DE VARIABLES TRADICIONALES QUE ES UN ENGORROSO y complejo, los arreglos permiten trabajar de maneras simple.
- Un arreglo es una secuencia ordenada de elementos
- Cuando los arreglos son bidimensionales, las estructuras de datos requieren dos índices para identificar a cada elemento de la lita o matriz que se forma
- Cuando se manejan arreglos multi dimenciionaes el primer indice corresponde a las filas y el segundo a las columnas
- Los métodos de ordenación pueden ser internos o externos
- Lo métodos de ordenamiento mas comunes son de selección, inserccion y burbuja
- Los métodos de búsqueda mas comunes son secuencia y binaria
- La selección de métodos de ordenacion y buqueda depende de la cantidad de datos, el tipo de datos y el orden que tengan
Búsqueda secuencial.
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 es localizado, 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:
algoritmo Método_Busqueda_secuencial
//declaraciones inicio
// lectura del vector
desde i ⭠ 1 hasta N hacer
leer ( vec[ i ] )
fin-desde
//se toma la clave de búsqueda leer ( clave)
//búsqueda ban ⭠ falso
desde i ⭠ 1 hasta n hacer
si vec [i ] = clave entonces
ban ⭠ verdadero
fin-si
fin-desde
si ban = verdadero entonces
mostrar ( „la clave de búsqueda está en el arreglo‟ )
si-no
mostrar ( „la clave de búsqueda NO está en el arreglo‟ )
fin-si
finNo te detengas, sigue avanzando
Aquí tienes un propósito para este 2024 que debes considerar seriamente: si has querido mejorar tus habilidades en hacking, Ciberseguridad y programación ahora es definitivamente el momento de dar el siguiente paso. ¡Desarrolla tus habilidades aprovechando nuestros cursos a un precio increíble y avanza en tu carrera!
Python Practicando. Desde 0 hasta Desarrollador en Python
Aprende Python, donde iniciamos desde 0, sin conocimientos previos hasta desarrollar aplicaciones con mucha practica!
Calificación: 4,6 de 5 (20.833 calificaciones) 249.493 estudiantes Creado por Alvaro Chirou • 1.800.000+ Enrollments Worldwide, Walter Coto || +450,000 Estudiantes Español.
Lo que aprenderás
- Ejercitar la lógica de programación
- Comprender cómo la vida cotidiana puede ser fácilitada o simulada con código
- Aprender programación desde cero
- Usar Visual Studio Code como Editor de Código
- Conocer y aprender el lenguaje de programación Python
- Ser un programador desde cero, sin conocimiento en otro lenguaje o con algo previo
- Mejorar las habilidades de programación, mejorar procesos y fácilitar la comprensión de código
- Preparar un entorno dónde programar en Python
- Operaciones aritméticas y jerarquía de Python
- Manejo de cadenas en Python
- Digitar datos por teclado con Python
- Mostrar Datos por Pantalla al usuario en Python
- Operadores Relacionales de Python
- Operadores Lógicos de Python
- Condicionales en Python
- Estructuras de Datos: Listas, Tuplas y Diccionarios
- Iteraciones y bucles repetitivos de Python
- Segmentar Código y hacerlo más eficaz con las Funciones en Python
- Gestionar posibles errores que puedan dar tus programas
- Programación Orientada a Objetos
- HTML y CSS
- Selenium Web Driver con Python
- Ejercitar todo lo Aprendido con Ejercicios
Este curso incluye:
- 25,5 horas de vídeo bajo demanda
- 21 artículos
- 148 recursos descargables
- Acceso en dispositivos móviles y TV
- Certificado de finalización
Python es Hoy uno de los lenguajes más utilizados por Excelencia.
Esto se debe por su simpleza al momento de Desarrollar aplicaciones.
Por su capacidad de procesamiento a altas velocidades con grandes volúmenes de información.
Es un increíble lenguaje con el cual si no sabes programar, podrás aprender.
Y si ya sabes desarrollar, te aconsejo aprenderlo ya que en el mercado cada vez se solicitan más desarrolladores en Python.
Aspirar al trabajo que desean, o mejorar sus ingresos con un aumento de salario.
Python se utiliza para muchisimas cosas como:
- Machine Learning
- Data Science
- Inteligencia Artificial.
- Y mucho más!
En este curso te acompañare en el proceso por el cual aprenderás las bases del lenguaje, para luego determinar qué camino quieres seguir.
Te invito que me acompañes a conocer este Gran Lenguaje!
Aprende con nuestros más de 100 cursos que tenemos disponibles para vos
¿Te gustaría enterarte de cuando lanzamos descuentos y nuevos cursos?
Sobre los autores
Álvaro Chirou
Yo soy Álvaro Chirou, tengo más de 20 Años de experiencia trabajando en Tecnología, eh dado disertaciones en eventos internacionales como OWASP, tengo más de 1.800.000 estudiantes en Udemy y 100 formaciones profesionales impartidas en la misma. Puedes serguirme en mis redes:
Laprovittera Carlos
Soy Laprovittera Carlos. Con más de 20 años de experiencia en IT brindo Educación y Consultoría en Seguridad de la Información para profesionales, bancos y empresas. Puedes saber más de mi y de mis servicios en mi sitio web: laprovittera.com y seguirme en mis redes:
¿Quieres iniciarte en hacking y ciberseguridad pero no sabes por dónde empezar? Inicia leyendo nuestra guia gratuita: https://achirou.com/como-iniciarse-en-ciberseguridad-y-hacking-en-2024/ que te lleva de 0 a 100. Desde los fundamentos más básicos, pasando por cursos, recursos y certificaciones hasta cómo obtener tu primer empleo.