• Author / Uploaded
• MateUCE

Citation preview

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