JUSTIFICACIÓN

El propósito de usar la búsqueda binaria es que un algoritmo de búsqueda que nos

permite encontrar la posición de un valor en un array ordenándolos y la importancia
que tiene los ordenamientos en particular el ordenamiento por el método Shell en
C++, es con el objetivo analizar la importancia que tiene estos ordenamiento ya que
nos permita conservar un orden y una eficacia muy buena, además nos permite una
fácil implementación y realizar pocos intercambios, reducir el código, lo cual es de
gran ayuda ya que nos permite realizar un mantenimiento adecuado y práctico al
momento de realizar un programa en C++.

El presente informe realizado se enfoca en conocer el funcionamiento de la

búsqueda binaria en C++ y para ello primero ordenamos de forma ascendente por
el método Shell ya que mediante este informe realizado determinamos que la
búsqueda binaria tiene como finalidad la búsqueda de un elemento en C++.

OBJETIVOS

Objetivo general:

Determinar la importancia y utilidad que tiene la búsqueda binaria, mediante

información obtenida en distintas fuentes bibliográficas, con la finalidad de
comprender su funcionamiento y especialmente su utilidad dentro de la
programación.

Objetivos específicos:

 Indagar en distintas fuentes bibliográficas para obtener información útil y

precisa que ayude al desarrollo del tema establecido.
 Analizar de una manera eficaz todo acerca del método de ordenación por
Shell, especialmente poniéndolas en práctica mediante la realización de
ejercicios eficaces.
 Determinar las características principales de la búsqueda por el método
Shell para de esta manera poder comprender su funcionamiento.
 MARCO TEORICO

1. Búsqueda binaria:

1.1 Concepto:

La búsqueda binaria, también conocida como búsqueda de intervalo medio 1 o

búsqueda logarítmica ,2 es un algoritmo de búsqueda que encuentra la posición de
un valor en un array ordenado. (Anónimo, 2017, pg.1)
1.1.1 Método Shell
El Shell es una generalización del ordenamiento por inserción, teniendo en cuenta
dos observaciones:
 El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
 El ordenamiento por inserción es ineficiente, en general, porque mueve los
valores sólo una posición cada vez.
El algoritmo Shell mejora el ordenamiento por inserción comparando elementos
separados por un espacio de varias posiciones. Esto permite que un elemento haga
"pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos
se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell
es un simple ordenamiento por inserción, pero para entonces, ya está garantizado
que los datos del vector están casi ordenados. (Soler Pellicer, 2009, pg.1)

1.2 Características de la búsqueda binaria

1. La búsqueda binaria funciona en arreglos ordenados
2. La búsqueda binaria comienza por comparar el elemento del medio del
arreglo con el valor buscado.
3. Si el valor buscado es igual al elemento del medio
4. su posición en el arreglo es retornada
5. Si el valor buscado es menor o mayor que el elemento del medio, la
búsqueda continua en la primera o segunda mitad, respectivamente
(Mendoza, H, 2016, pg.1)
1.3 Funcionamiento de la búsqueda binaria:

int vector[10] = {2,4,6,8,10,12,14,16,18,20};

La clave que queremos buscar es 6. El algoritmo funciona de la siguien manera

1. Se determinan un indice arriba y un indice abajo, Iarriba=0 e Iabajo=9

respectivamente.
2. Se determina un indice central, Icentro = (Iarriba + Iabajo)/2, en este caso
quedaría I centro = 4.
3. Evaluamos si vector[Icentro] es igual a la clave de busqueda, si es igual ya
encontramos la clave y devolvemos Icentro.
4. Si son distintos, evaluamos si vector[Icentro] es mayor o menos que la
clave, como el arreglo está ordenado al hacer esto ya podemos descartar una
mitad del arreglo asegurándonos que en esa mitad no está la clave que
buscamos. En nuestro caso vector[Icentro] = 4 < 6, entonces la parte del
arreglo vector[0...4] ya puede descartarse.
5. Reasignamos I arriba o I abajo para obtener la nueva parte del arreglo en
donde queremos buscar. I arriba, queda igual ya que sigue siendo el tope.
Iabajo lo tenemos subir hasta 5, entonces quedaria Iarriba = 9, Iabajo = 5. Y
volvemos al paso 2. (Anónimo, 2017, pg.3)
1.4. SINTAXIS:

// Código C++:

int numeros[20];
int inf,sup,mitad,dato,i,j,n;
char band='F';
cout<<"ingrese el tamanio del vector: ";cin>>n;
cout<<endl;
for(i=0;i<n;i++){
cout<<" Elemento ["<<i<<"]=";
cin>>numeros[i];
}
cout<<"\n\nIngrese el numero que quiere Buscar: ";cin>>dato;
inf=0;
sup=5;
i=0;
while((inf<=sup)&&(i<n)){
mitad = (inf+sup)/2;
if(numeros[mitad] == dato){
band='V';
break;
}
if(numeros[mitad]>dato){
sup = mitad;
mitad = (inf+sup)/2;
}
if(numeros[mitad]<dato){
inf = mitad;
mitad = (inf+sup)/2;
}
i++;
}

if(band == 'V'){

j=mitad;

cout<<"El numero es: "<<dato<<" Y se encontro en la posicion :

"<<dato<<endl;
}
else{
cout<<"El numero NO se encontro";
}

De esta manera podemos buscar un elemento en un vector.

//Algoritmo:

Definir como entero a numeros[20]

Definir como entero a inf,sup,mitad,dato,i,j,n
Definir como cadena a band='f'

Escribir 'Ingrese el tamanio del Vector '

leer n

Para (i=0 hasta i<n con incremento de i++ hacer)

Escribir' Elemento[',i']'
Leer numeros[i]
Fin Para

Escribir'Ingrese el numero que quiere buscar'

inf=0
sup=n
i=0

Mientras ((inf<=sup)and(i<n)) Hacer

mitad = (inf+sup)/2;
Si (numeros[mitad] == dato) Hacer
band='V'
Fin Si

Si (numeros[mitad]>dato) Hacer
sup = mitad;
mitad = (inf+sup)/2
Fin Si

Si (numeros[mitad]<dato) Hacer
inf = mitad;
mitad = (inf+sup)/2;
Fin si

i++

Fin Mientras

Si (band == 'V') Hacer

j=mitad;

Escribir'"El numero es: ',dato,' Y se encontro en la posicion :',mitad

Sino Hacer
Escribir'El numero NO se encontro'
Fin Si
1.5. Análisis del algoritmo:

 El algoritmo permite buscar un elemento de una lista de arrays para ello

primero debe estar ordenado la lista o si no se podrá hacer la búsqueda
binaria lo cual permite que sea más rápido a la hora de ejecución y también
proporciona un medio para reducir el tiempo requerido para buscar en una
lista o vector.

1.6 Ventajas:

 La búsqueda binaria es un método eficiente siempre que el vector esté

ordenado.
 La búsqueda binaria proporciona un medio para reducir el tiempo requerido
para buscar en una lista
 Es más rápido por su recursividad, su mayor ventaja es con los archivos
extensos.
 El código del procedimiento de esta búsqueda es corto en comparación con
las demás técnicas de búsqueda

1.7 Desventajas:

 El archivo debe estar ordenado y el almacenamiento de un archivo ordenado

suele plantear problemas en las inserciones y eliminaciones de elementos.
 No revisa todos los elementos del archivo, requiere que todos los elementos
estén ordenados
EJERCICIO:

1. Ingrese tres vectores por teclado y el 1er y 2do vector multiplíquelos y con
el resultado obtenido restamos del vector 3 y con el resultado que obtenemos
aplicar el ordenamiento por el método Shell para de esta manera realizar la
Búsqueda Binaria de un número.

Codificación:

#include<iostream>
#include<conio.h>
#include<stdio.h>
#include<cmath>
#include<stdbool.h>

using namespace std;

void ingreso();
void proceso(int vec1[],int vec2[],int vec3[],int vec4[],int vec5[]);
void shell(int vec5[]);
void busqueda_binaria(int vec5[]);
void imprimir(int vec1[],int vec2[],int vec3[],int vec4[],int vec5[]);

int dato,inf,sup,mitad;
char band='F';
int i,n;
int vector1[20],vector2[20],vector3[20],vector4[20],vector5[20];
char op='s';

int main()
{
presentacion();
system("cls");
cout<<"\n --------------------> OPERACIONES CON VECTORES <--------------------
--"<<endl;
cout<<" !BIENVENIDO!"<<"\n\n";
cout<<"Antes de empezar debes recordar que: "<<"\n\n";
cout<<" METODO SHELL:"<<endl;
cout<<" | Es un algoritmo de ordenamiento. Su implementacion
|"<<endl;
cout<<" | original, requiere 0(n^2) comparaciones |"<<endl;
cout<<" | e intercambios en el peor caso. |"<<"\n\n";
cout<<" BUSQUEDA BINARIA:"<<endl;
cout<<" | Solo se puede implementar si el arreglo esta |"<<endl;
cout<<" | ordenado. La idea consiste en ir dividiendo |"<<endl;
cout<<" | el arreglo en mitades |"<<"\n\n";
cout<<" !MUY BIEN EMPEZEMOS!"<<"\n\n";
 system("pause");

ingreso();
proceso(vector1,vector2,vector3,vector4,vector5);
imprimir(vector1,vector2,vector3,vector4,vector5);

getch();
return 0;
}

void ingreso()
{
system("cls");
system("color 3f");
cout<<"\n --------------------> OPERACIONES CON VECTORES <--------------------
--"<<endl;
cout<<" !BIENVENIDO!"<<"\n\n";

cout<<"Ingrese el tamanio de los vectores: ";

while((cin>>n).fail())
{
cin.clear();
fflush(stdin);
cout<<"\n!Error! Porfavor ingrese solo numeros"<<"\n\n";
cout<<"Ingrese el tamanio de los vectores: ";
}

cout<<endl;
cout<<" VECTOR_1: "<<"\n\n";
for(i=0;i<n;i++)
{
cout<<" Posicion ["<<i<<"]: ";

while((cin>>vector1[i]).fail())
{
cin.clear();
fflush(stdin);
cout<<"\n!Error! Porfavor ingrese solo numeros"<<"\n\n";
cout<<" Posicion ["<<i<<"]: ";
}
}

cout<<"\n\n";
cout<<" VECTOR_2: "<<"\n\n";
for(i=0;i<n;i++)
{
cout<<" Posicion ["<<i<<"]: ";

while((cin>>vector2[i]).fail())
{
 cin.clear();
fflush(stdin);
cout<<"\n!Error! Porfavor ingrese solo numeros"<<"\n\n";
cout<<" Posicion ["<<i<<"]: ";
}
}

cout<<"\n\n";
cout<<" VECTOR_3: "<<"\n\n";
for(i=0;i<n;i++)
{
cout<<" Posicion ["<<i<<"]: ";

while((cin>>vector3[i]).fail())
{
cin.clear();
fflush(stdin);
cout<<"\n!Error! Porfavor ingrese solo numeros"<<"\n\n";
cout<<" Posicion ["<<i<<"]: ";
}
}
cout<<"\n\n";
system("pause");
}

void proceso(int vec1[],int vec2[],int vec3[],int vec4[],int vec5[])

{
for(i=0;i<n;i++)
{
vec4[i]=vec1[i]*vec2[i];
}
for(i=0;i<n;i++)
{
vec5[i]=vec4[i]-vec3[i];
}
}

void shell(int vec5[])

{
int ints,aux;
bool band;

ints=n;

while(ints>1)
{
ints=(ints/2);
band=true;

while(band==true)
 {
band=false;
i=0;

while((i+ints)<n)
{
if(vec5[i]>vec5[i+ints])
{
aux=vec5[i];
vec5[i]=vec5[i+ints];
vec5[i+ints]=aux;
band=true;
}
i++;
}
}
}
}

void busqueda_binaria(int vec5[])

{
//Algoritmo de busqueda binaria
inf=0;
sup=n;

while(inf<=sup)
{
mitad=(inf+sup)/2;

if(vec5[mitad]==dato)
{
band='V';
break;
}
if(vec5[mitad]>dato)
{
sup=mitad;
mitad=(inf+sup)/2;
}
if(vec5[mitad]<dato)
{
inf=mitad;
mitad=(inf+sup)/2;
}
}
}

void imprimir(int vec1[],int vec2[],int vec3[],int vec4[],int vec5[])

{
system("cls");
 system("color 3f");
cout<<"\n --------------------> OPERACIONES CON VECTORES <--------------------
--"<<endl;
cout<<" !BIENVENIDO!"<<"\n\n";
cout<<" VECTOR_1: "<<"\n\n";
for(i=0;i<n;i++)
{
cout<<" "<<vec1[i];
}

cout<<"\n\n";
cout<<" VECTOR_2: "<<"\n\n";
for(i=0;i<n;i++)
{
cout<<" "<<vector2[i];
}

cout<<"\n\n";
cout<<" VECTOR_3: "<<"\n\n";
for(i=0;i<n;i++)
{
cout<<" "<<vector3[i];
}
cout<<"\n\n";

cout<< " --> El producto de VECTOR_1 y VECTOR_2 es: "<< "\n\n";

for(i=0;i<n;i++)
{
cout<<" "<<vec4[i];
}

cout<<"\n\n";
cout<<" --> La diferencia entre (VECTOR_1*VECTOR_2) - VECTOR_3 es:";
cout<<"\n\n";
for(i=0;i<n;i++)
{
cout<<" "<<vec5[i];
}

//ORDENAMIENTO POR SHELL

shell(vec5);

cout<<"\n\n";
cout<<" [El vector ordenado ascendentemente] "<<"\n\n";
for(i=0;i<n;i++)
{
cout<<" "<<vec5[i];
}

//BUSQUEDA BINARIA
 cout<<"\n\n";
cout<<" Ingrese el elemento que desee buscar: ";cin>>dato;

cout<<"\n\n";
busqueda_binaria(vec5);

if(band=='V')
{
cout<<" El numero: " << dato << ", Ha sido encontrado en la posicion
["<<mitad<<"] "<<"\n\n";
}else
if(band=='F')
{
cout<<" Dato no encontrado"<<"\n\n";
}

system("pause");
cout<<"\n\n";
cout<<"Desea realizar un nuevo proceso??"<<endl;
cout<<" S/s=si"<<endl;
cout<<" N/n=no"<<endl;
cout<<"OP: ";cin>>op;

if(op=='s'||op=='S')
{
ingreso();
proceso(vector1,vector2,vector3,vector4,vector5);
imprimir(vector1,vector2,vector3,vector4,vector5);
}else
{
cout<<"\n\n !GRACIAS POR TU VISITA!"<<endl;
cout<<" !VUELVE PRONTO!"<<"\n\n";
system("pause");
}
}

EJECUCIÓN:
MAPA MENTAL
 Bibliografía

Mendoza, H. (2016). Caracteristica busqueda binaria. Madrid: Untitled Prezi.

Anónimo. (2017).Busqueda Binaria. Madrid: Wikilibros.
Soler Pellicer, Y., Brito, L., & Gerónimo, M. (2009).Método Shell en C++. No
Solo Usabilidad, (8).

Conclusiones
 Del informe realizado se determinó que la búsqueda binaria es un método
eficiente ya que nos permite buscar un elemento en una lista de arrays esto
lo realiza siempre y cuando el vector o lista de arrays esté ordenada.

 El método de Shell se lo puede aplicar en una lista de arrays para así poder
implementar la búsqueda binaria ya que el método Shell permite que un
elemento haga "pasos más grandes" hacia su posición esperada. Los pasos
múltiples sobre los datos se hacen con tamaños de espacio cada vez más
pequeños.

 La búsqueda binaria proporciona un medio para reducir el tiempo requerido

para buscar en una lista ya que es más rápido por su recursividad, esto
permite dar una mayor ventaja es con los archivos extensos.