• Author / Uploaded
• Daniel Morfa Vega

Citation preview

Seminario Estructura de datos I

Búsqueda binaria: bisección, logarítmica o dicotómica.

Autor: Daniel Morfa Vega

Indice:

Definición de algoritmo de búsqueda. Definición y análisis de búsqueda binaria. Ventajas. Desventajas. Aplicaciones del algoritmo de búsqueda binaria. Implementación. ◦ Pseudocódigo ◦ Diagrama de flujo. ◦ Implementación en lenguajes. • Ejemplos de su uso. • • • • • •

Definición de algoritmo de búsqueda: Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos. Consiste en solucionar un problema de existencia o no de un elemento determinado en un conjunto finito de elementos, es decir, si el elemento en cuestión pertenece o no a dicho conjunto, además de su localización dentro de éste.

Definición de búsqueda binaria: Este mecanismo de búsqueda puede ser utilizado cuando el vector en el que queremos determinar la existencia o no de un elemento está ordenado, o puede estarlo, este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente con el número de iteraciones. La estrategia consiste en comparar X con el elemento del medio del array, si es igual entonces encontramos el elemento, sino, cuando X es menor que el elemento del medio aplicamos la misma estrategia al array a la izquierda del elemento del medio y si X es mayor que el elemento del medio aplicamos la misma estrategia al array a la derecha de dicho elemento.

Análisis de la búsqueda binaria: El caso mejor se presenta cuando una coincidencia se encuentra en el punto central de la lista. En este caso la complejidad es O(1) dado que sólo se realiza una prueba de comparación de igualdad. La complejidad del caso peor es O(log2 n) que se produce cuando el elemento no está en la lista o el elemento se encuentra en la última comparación. En este caso se debe continuar la búsqueda y llegar a una sublista de longitud 1. Cada iteración que falla debe continuar disminuyendo la longitud de la sublista por un factor de 2. El tamaño de las sublistas es: n n/2 n/4 n/8 . . . 1

La división de sublistas requiere m iteraciones, en cada iteración el tamaño de la sublista se reduce a la mitad. La sucesión de tamaños de las sublistas hasta una sublista de longitud 1: n n/2 n/2 n/23 n/24 ... n/2m

siendo n/2m = 1. Tomando logaritmos en base 2 en la expresión anterior quedará: n = 2m m = log2 n

Por esa razón la complejidad del caso peor es O(log2 n). Cada iteración requiere una operación de comparación: Total comparaciones ~ 1 + log2 n

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 mas 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.

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

Aplicaciones: Ejemplo: Árbol Binario de Búsqueda: Se distinguen 2 casos triviales con solución directa: árbol vacío (elemento no encontrado) o raíz del árbol. Solución: Cuando el elemento no se encuentra en la raíz, dividimos el árbol en 2 subarboles (izquierda y derecha) y aplicamos ABB, sobre aquel que nos interese (al estar ordenado solo debemos ir por una de las ramas). La combinación de resultados es trivial: la solución del subproblema es también la del problema global; Supongamos la lista siguiente: {1231,1473,1545,1834,1892,1898,1983,2005,2446,2685,3200} donde el elemento central es 1898 Si está buscando el elemento 1983, se examina el número central 1898 en la sexta posición. Ya que 1983 es mayor que 1898, se desprecia la primera sublista y nos centramos en la segunda {1983,2005,2446,2685,3200} donde el elemento central es 2446 El número central de esta sublista es 2446 y el elemento buscado es 1983 menos que 2446; eliminamos la segunda sublista y nos queda {1983,2005} Como no hay término central elegimos el término inmediatamente anterior al término central, 1983, que es el buscado. Se han necesitado tres comparaciones, mientras que en otras búsquedas como la secuencial hubiese necesitado siete.

Implementación: Pseudocódigo: Comenzar Leer X Ingresar V(I) I = 1,100 ULTIMO = 100 PRIMERO = 1 Hasta PRIMERO X Entonces ULTIMO = CENTRAL – 1 Si_no PRIMERO = CENTRAL + 1 Fin_si Fin_Hasta Imprimir “Registro no encontrado” Parar

Diagrama de flujo:

Implementación en lenguajes: C++: #include bool busqueda_binaria(const vector &v, int principio, int fin, int &x){ bool res; if(principio v[m]) res = busqueda_binaria(v, m+1, fin, x); else res = true; }else res = false; return res; } /*{Doc: Si se encuentra el valor devuelve true, sino false}*/

C: int busquedaBinaria(int vector[], int n, int dato) { int centro,inf=0,sup=n-1; while(inf numeros [centro]): return busquedaBinaria (numeros, centro + 1, fin, elemento) else: return True def busqueda (numeros, elemento): if (numeros == None) or (numeros == []): return False else: return busquedaBinaria (numeros, 0, len (numeros) - 1, elemento)

Ejemplo de uso: .h class BusquedaBin { private: int central; int bajo; int alto; int ValorCentral; public: BusquedaBin(); int BusquedaBinaria(int lista[], int n, int clave); };

.cpp int BusquedaBin::BusquedaBinaria(int lista[], int n, int clave) { this->bajo = 0; this->alto = n-1; while (this->bajo alto) { this->central = (this->bajo + this->alto)/2; /* índice de elemento central */ this->ValorCentral = lista[this->central]; /* valor del índice central */ if (clave == this->ValorCentral) return this->central; /* encontrado, devuelve posición */ else if (clave < this->ValorCentral) this->alto = this->central -1; /* ir a sublista inferior */ else this->bajo = this->central + 1; /* ir a sublista superior */ } return -1; /* elemento no encontrado */ }