Busqueda Binaria 3v1o3a

Búsqueda binaria en java Implementación del algoritmo de búsqueda binaria de manera no recursiva en Java. Se utiliza una función estática de la clase BusquedaAlgoritmo. Recordar que para que funcione correctamente los valores del arreglo deben estar ordenados. class BusquedaAlgoritmo { public static int buscar( int [] arreglo, int dato) { int inicio = 0; int fin = arreglo.length - 1; int pos; while (inicio <= fin) { pos = (inicio+fin) / 2; if ( arreglo[pos] == dato ) return pos; else if ( arreglo[pos] < dato ) { inicio = pos+1; } else { fin = pos-1; } } return -1; } } public class BusquedaBinaria { public static void main (String args[]) { // Llenar arreglo int [] edades = new int [35]; for (int i = 0; i < edades.length ; i++) edades[i] = i*i ; // Mostrar arreglo. for (int i = 0; i < edades.length ; i++) System.out.println ( "edades["+i+"]: "+

edades[i]);

int resultado = BusquedaAlgoritmo.buscar(edades, 9); if (resultado != -1) { System.out.println ( "Encontrado en: "+ resultado); } else { System.out.println ( "El dato no se encuentra en el arreglo, o el arreglo no está ordenado." ); } } }

Búsqueda binaria o dicotómica Para utilizar este algoritmo, el array debe estar ordenado. La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el

elemento con el del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo. Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos: Se toma el elemento central y se divide el array en dos: {1,2,3,4}−5-{6,7,8,9} Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4} Se vuelve a dividir el array en dos: {1}−2-{3,4} Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4} Se vuelve a dividir en dos: {}−3-{4} Como el elemento buscado coincide con el central, lo hemos encontrado. Si al final de la búsqueda todavía no lo hemos encontrado, y el subarray a dividir está vacio {}, el elemento no se encuentra en el array. La implementación sería: int desde,hasta,medio,elemento,posicion; // desde y // hasta indican los límites del array que se está mirando.

int array[N]; // Dar valor a elemento. for(desde=0,hasta=N-1;desde<=hasta;) { if(desde==hasta) // si el array sólo tiene un elemento: { if(array[desde]==elemento) // si es la solución: posicion=desde; // darle el valor. else // si no es el valor: posicion=−1; // no está en el array. break; // Salir del bucle. } medio=(desde+hasta)/2; // Divide el array en dos. if(array[medio]==elemento) // Si coincide con el central: { posicion=medio; // ese es la solución break; // y sale del bucle. } else if(array[medio]>elemento) // si es menor: hasta=medio-1; // elige el array izquierda. else // y si es mayor: desde=medio+1; // elige el array de la derecha. }

Búsqueda Binaria Uno de los algoritmos de búsqueda más eficiente que existe en la estructura de datos es la búsqueda binaria, las características para poder implementar este algoritmo son las siguientes: • •

Los datos deben estar contenido en un estructura de datos tipo vector Los datos del vector deben estar ordenados

Una vez que se cuenten son las características descritas, se divide el vector para poder

conocer la posición central y se verifica si es el dato que se esta buscando (lineas 9-12), si es el dato que se busca regresa la posición (índice del vector), en caso de que no sea el dato que buscamos se verifica si es mayor o menor que la posición central y se vuelve a redefinir la posición final o inicial según cumpla la condición (lineas 14-18). 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, de la misma manera si el dato que buscamos en menor que la posición central definida se descarta la parte superior del vector. Una vez que encuentre el dato el método regresara la posición en que lo encontró (linea 12), en caso de no encontrar el dato en el vector regresara el valor -1

La implementación de este ejemplo del algoritmo de búsqueda binaria se encuentra en el lenguaje de programación Java.