ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA MECÁNICA
PROGRAMACIÓN
DESCRIPCIÓN: EJERCICIOS, DEBER 3
NOMBRE: ANDRÉS MARCELO AULESTIA UBILLUS
FECHA: 2023/08/07
TEMA: PROGRAMACIÓN ESTRUCTURADA, ALGORITMOS DE ORDENAMIENTO Y
BÚSQUEDA.
INTRODUCCIÓN
La programación estructurada en conjunto con las estructuras de control y
estructuras repetitivas son un método de escritura de código eficiente para reducir
la extensión de este a una serie de instrucciones compactas que usualmente se
rigen con condiciones lógicas.
Se realizará un ejercicio de búsqueda binaria el cual es un algoritmo eficiente para
encontrar un elemento en una lista ordenada de elementos. Funciona al dividir
repetidamente a la mitad la porción de la lista que podría contener al elemento,
hasta reducir las ubicaciones posibles a solo una.
DESARROLLO
EJERCICIO 1:
Realizar el algoritmo de búsqueda binaria, para lo cual el usuario deberá ingresar
por el teclado tanto el número de elementos de un vector, así como los mismos.
Luego le pedirá al usuario el número a buscar (X), y como resultado se indicará si X
se encuentra o no en el vector, de encontrarse en el mismo, se indicará la posición
en la que se encuentre.
La búsqueda binaria es un algoritmo eficiente para encontrar un elemento en una lista
ordenada de elementos. Funciona al dividir repetidamente a la mitad la porción de la lista
que podría contener al elemento, hasta reducir las ubicaciones posibles a solo una.
Se puede analizar este problema de la siguiente manera:
Semestre 2023-A 1
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA MECÁNICA
1) Se ingresa el numero de elementos que se desean guardar en el vector (n)
2) Se ingresan los elementos en el vector
3) Se ordenan los elementos del vector de manera ascendente o descendente, en
nuestro caso se ordenará de forma ascendente
4) Se realizará el algoritmo de la búsqueda binaria
5) Se imprimirá el numero de la posición donde se encuentre el elemento a buscar en
el vector ordenado
Para el algoritmo de la búsqueda binaria es necesario que el arreglo esté ordenado para
ello utilizaremos un ordenamiento simple utilizando dos bucles for, con contadores i y j
que empiecen en 0 y terminen en un valor menor que n-1 respectivamente para que
analicen cada repetición de filas y los elementos de cada fila. Si el elemento de la posición
v [ j ] < v [ j+1] se utilizará una variable auxiliar (aux) y se cambiará la posición del elemento
de la siguiente manera:
aux=v [ j+1];
v [ j+ 1]=v [ j];
v [ j]=aux ;
Una vez ordenado el vector se procede a crear la variable max que es igual a n-1 un ciclo
for que analice el vector n-1 veces, luego analizo si mi numero a buscar no se encuentra
en los extremos con un condiciona if
1. Si el valor que busco está en la posición v[min] imprimo la posición min+1 y
uso un break para romper todo el ciclo
2. Si el valor está en la posición v[max] imprimo max+1 uso break y se rompe el
ciclo
Si el valor no se encuentra en los extremos procedemos a definir la variable mid como el
valor (min+max)/2 , dado que la declararemos como un entero nos presentara la parte
entera inferior de la división y con ello creamos tres condicionales if que representan las
tres posibles opciones para el número a buscar:
1. Si el numero de v[mid] es igual al numero que buscamos entonces imprimo la
posición mid+1 y uso un break para romper todo el ciclo.
2. Si el valor no se encuentra en v[mid] entonces el valor es mayor o menor:
a. Si es menor a v[mid] entonces defino a max como max=mid y corre de
nuevo el ciclo.
b. Si es mayor a v[mid] entonces defino a min como min=mid y va de
nuevo el ciclo.
Ahora dentro del ciclo for si ninguna de estas condiciones se cumple quiere decir que el
numero no se encuentra en el vector, para esto utilizo un condicional else al final e
imprimo el mensaje de que no se encuentra el número en el vector.
Para el ilustrar el algoritmo en el pseudocódigo se realiza el siguiente ejemplo:
Semestre 2023-A 2
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA MECÁNICA
Se ingresará 8 elemento ordenados de la siguiente manera: 5,4,3,2,1,0,6,7 y se pedirá
encontrar el elemento 4 que se posicionará en el 6to puesto.
v=[ 5 , 4 , 3 , 2, 1 , 0 ,6 ,7 ]
Con lo cual el psuedocódigo queda así:
Semestre 2023-A 3
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA MECÁNICA
Semestre 2023-A 4
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA MECÁNICA
Semestre 2023-A 5
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA MECÁNICA
Semestre 2023-A 6
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA MECÁNICA
Realizando el mismo algoritmo en c++ obtenemos:
Semestre 2023-A 7
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA MECÁNICA
Semestre 2023-A 8
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA MECÁNICA
CONCLUSIONES
Importancia de la Programación Estructurada: El ejercicio abordado resalta la
importancia de la programación estructurada como un enfoque eficiente para
escribir código. La segmentación del código en bloques lógicos y el uso de
estructuras de control ayudan a crear programas más comprensibles y
mantenibles.
Semestre 2023-A 9
ESCUELA POLITÉCNICA NACIONAL
FACULTAD DE INGENIERÍA MECÁNICA
Algoritmos de Búsqueda y Ordenamiento: El ejercicio se centra en la
implementación y comprensión de algoritmos de búsqueda (en este caso, la
búsqueda binaria) y de ordenamiento (como el ordenamiento por burbuja). Estos
algoritmos son fundamentales en la optimización de la búsqueda y manipulación
de datos en arreglos.
Eficiencia y Reducción de Complejidad: La búsqueda binaria se presenta como un
ejemplo de algoritmo eficiente para encontrar elementos en una lista ordenada. La
reducción de las ubicaciones posibles a través de divisiones repetidas contribuye a
la eficiencia del proceso de búsqueda, especialmente en comparación con la
búsqueda lineal.
Semestre 2023-A 10
