Búsqueda binaria

Un árbo binario es aquel tipo de árbol en el que sus nodos solamente pueden tener cero, uno o dos nodos hijos.
El interés de los árboles binarios de búsqueda (ABB) radica en que su recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.
La búsqueda en árboles binarios es un método de búsqueda simple, dinámico y eficiente considerado como uno de los fundamentales en Ciencia de la Computación. De toda la terminología sobre árboles, tan sólo recordar que la propiedad que define un árbol binario es que cada nodo tiene a lo más un hijo a la izquierda y uno a la derecha. Para construir los algoritmos consideraremos que cada nodo contiene un registro con un valor clave a través del cual se efectuaran las búsquedas.

Aplicaciones de árboles binarios
Un árbol binario es una estructura de datos útil cuando se trata de hacer modelos de procesos en donde se requiere tomar decisiones en uno de dos sentidos en cada parte del proceso. Por ejemplo, supongamos que tenemos un arreglo en donde queremos encontrar todos los duplicados. Esta situación es bastante útil en el manejo de las bases de datos, para evitar un problema que se llama redundancia.
Una manera de encontrar los elementos duplicados en un arreglo es recorrer todo el arreglo y comparar con cada uno de los elementos del arreglo. Esto implica que si el arreglo tiene elementos, se deben hacer comparaciones, claro, no es mucho problema si es un número pequeño, pero el problema se va complicando más a medida que aumenta.
Si usamos un árbol binario, el número de comparaciones se reduce bastante, veamos cómo.
El primer número del arreglo se coloca en la raíz del con sus subárboles izquierdo y derecho vacíos. Luego, cada elemento del arreglo se compara son la información del nodo raíz y se crean los nuevos hijos con el siguiente criterio:

Si el elemento del arreglo es igual que la información del nodo raíz, entonces notificar duplicidad.
Si el elemento del arreglo es menor que la información del nodo raíz, entonces se crea un hijo izquierdo.
Si el elemento del arreglo es mayor que la información del nodo raíz, entonces se crea un hijo derecho.

La búsqueda lineal probablemente es sencilla de implementar e intuitiva. Básicamente consiste en buscar de manera secuencial un elemento, es decir, preguntar si el elemento buscado es igual al primero, segundo, tercero y así sucesivamente hasta encontrar el deseado. Entonces este algoritmo tiene una complejidad de O(n).


La búsqueda binaria al igual que otros algoritmos como el quicksort utiliza la técnica divide y vencerás. Uno de los requisitos antes de ejecutar la búsqueda binaria, es que el conjunto de elementos debe de estar ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector:
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 siguiente manera:

Su tiempo es (log2 n)
- Se busca el elemento del centro de la lista.
-Si es el buscado, se devuelve Si es mayor que el buscado (6), se repite la búsqueda sobre la primera mitad de la lista.
-Si es menor que el buscado (6), se repite la búsqueda sobre la segunda mitad de la lista.
-Se repite el algoritmo hasta que se encuentra el elemento o se llega a una lista de longitud cero (el elemento no existe).

Este proceso se resume de la siguiente forma: comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.




http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/arb_BB.htm
http://computacion.cs.cinvestav.mx/~acaceres/courses/estDatosCPP/node53.html
http://www.mailxmail.com/curso-aprende-programar/metodos-ordenamiento-busqueda