Documento Busqueda Binaria Pdf lqb

0

Contenido

Pág.

INTRODUCCIÓN ................................................................................................................ 2

OBJETIVOS............................................................................................................................ 3

¿QUÉ ES UN ALGORITMO DE BÚSQUEDA? ................................................... 4

EL ALGORITMO DE BÚSQUEDA BINARIA FUNCIONA DE LA

SIGUIENTE MANERA:.................................................................................................... 4

ALGORITMO DE BÚSQUEDA BINARIA EN JAVA ....................................... 5

EJERCICIO DEL ALGORITMO DE BÚSQUEDA BINARIA ....................... 6

VENTAJAS ................................................................................................... 7

DESVENTAJA ............................................................................................. 7

CONCLUSIONES ................................................................................................................ 8

RECOMENDACIONES .................................................................................................... 9

BIBLIOGRAFÍA ................................................................................................................. 10

1

INTRODUCCIÓN La recuperación de información es una de las aplicaciones más importantes de las computadoras. La búsqueda de información está relacionada con las tablas para consultas. Estas tablas contienen una cantidad de información que se almacenan en forma de listas de parejas de datos. Por ejemplo un catálogo con una lista de libros de matemáticas, en donde es necesario buscar con frecuencia elementos en una lista. Existen diferentes tipos de búsqueda, pero en este informe describiremos sólo la de tipo de búsqueda binaria.

2

OBJETIVOS

 Definir que es un algoritmo de búsqueda.  Dar a conocer cómo funciona el algoritmo de búsqueda binaria.  Describir el algoritmo en java.  Mostrar un ejercicio para una mejor comprensión del mismo.

 Describir las ventajas y desventajas del algoritmo de búsqueda binaria.

3

¿QUÉ ES UN ALGORITMO DE BÚSQUEDA? Es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos. Ejemplo: Ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez. Se le asigna el nombre de búsqueda binaria por que el algoritmo divide en dos al arreglo.

EL ALGORITMO DE BÚSQUEDA BINARIA FUNCIONA DE LA SIGUIENTE MANERA:

1. Se declaran los índices superior e inferior. El inferior que inicia en cero y el superior con el tamaño del arreglo menos 1.

2. Se

calcula

el

centro

del

arreglo

con

la

siguiente

fórmula.

Centro= (inferior + superior) / 2

3. Se verifica si el arreglo en la posición centro es igual al dato o elemento que se desea encontrar. Si es igual significa que encontramos el elemento. y retornamos centro.

4. Debido a que el vector se encuentra ordenado si el dato que buscamos es mayor a la posición central se descartan todos los datos que se encuentren en la parte inferior, ahora la variable inicio se ubica en la posición centro + 1 de la misma manera si el dato que buscamos en menor que la posición central definida se descarta la parte superior del vector, ahora la variable final se moverá a la izquierda y se ubica en la posición centro - 1.

5. Volvemos al paso 2, hasta encontrar el dato que buscamos.

4

ALGORITMO DE BÚSQUEDA BINARIA EN public static void main(String[] args) { intarr[]={3,6,9,11,13,16,18,20,23,26,30,37,45,85,90,93,97, 101,128,356}; int pos_ini=0; int pos_fin=arr.length-1; int pos_centro; int num = 85; while(pos_ini<=pos_fin) { pos_centro = (pos_ini+pos_fin)/2; if(arr[pos_centro]== num) { System.out.println("Elemento encontrado en la posición\n"+pos_centro); break; } else { if(num < arr[pos_centro]) pos_fin = pos_centro - 1; else { pos_ini = pos_centro + 1; } } } }

5

EJERCICIO DEL ALGORITMO DE BÚSQUEDA BINARIA Se quiere buscar el 10 en el siguiente arreglo: 3

5

10

15

21

50

100

1564

1565

100000

50

100

1564

1565

100000

Paso 1: La búsqueda binaria busca la mitad: 3

5

10

15

21

Si es el resultado devuelve su posición, en otro caso busca de qué lado está el valor, y desecha la mitad del arreglo Paso 2: busca la mitad. 3

5

10

15

Si es el resultado devuelve su posición, en otro caso busca de qué lado está el valor, y desecha la mitad del arreglo Paso 3: busca la mitad. 10

15

Como se encontró el resultado, se regresa su posición que es la 3.

6

VENTAJAS  La búsqueda binaria es un método eficiente siempre y cuando el arreglo este ordenado de manera ascendente.  La búsqueda binaria proporciona un medio para reducir al máximo el tiempo necesario para buscar un elemento dentro de una lista de gran tamaño.

 Esta altamente recomendado para buscar en arreglos extremadamente extensos ya que si se tiene un arreglo de más 100 elementos, este en una sola iteración desecha la mitad del arreglo reduciendo elementos y de esta manera tiempo.

DESVENTAJA  El arreglo debe estar necesariamente ordenado de manera ascendente.

7

CONCLUSIONES

 En la búsqueda binaria la eficiencia es muy alta porque el rango de búsqueda se

divide en dos en cada iteración, por lo tanto se consigue encontrar al elemento mucho más rápido.  La eficiencia de un algoritmo de búsqueda depende de si el arreglo sobre el que hacemos la búsqueda está o no ordenado.  El algoritmo de búsqueda binaria es excelente para arreglos extensos ya que en una sola iteración divide el arreglo en dos y de esta manera reduce su dimensión, y el tiempo de búsqueda del elemento deseado.

8

RECOMENDACIONES

 Antes de realizar una búsqueda empleando el algoritmo binario se debe verificar que es arreglo este ordenado de manera ascendente.

 Utilizar un algoritmo de búsqueda de acuerdo a sus necesidades para una mejor eficiencia en la búsqueda de elementos y procesamiento de la misma.  Es recomendable utilizar este método de búsqueda con archivos muy extensos ya que proporciona un medio para reducir el tiempo de búsqueda, debido a que en una sola iteración elimina el 50 % de elementos de una lista o arreglo que se está ejecutando.

9

BIBLIOGRAFÍA  Larre. (2011). Algoritmo de búsqueda binaria, Universidad del Cauca recuperado el: 10, julio, 2014. URL http://artemisa.unicauca.edu.co/~nediaz/EDDI/cap02.htm  Domínguez. (2013). Aplicaciones, algoritmo de búsqueda binaria, recuperado el 10, julio, 2014.URL http://algorithmmx.blogspot.com/2011/11/algoritmo-de-busqueda-binaria.html

10