Búsqueda Binaria

La búsqueda binaria, también llamada dicotómica,  es de los algoritmos de búsqueda más eficientes que hay. Para poder llevarla a cabo, es necesario que los elementos del vector estén ordenados previamente, ya sea de forma ascendente o descendente.

Estos son los pasos que se llevan a cabo en este tipo de búsqueda:

1. Se divide el vector en dos partes iguales.
2. Si el elemento en el centro del vector es mayor que el del elemento buscado, busca en la primera mitad.
3. Si el elemento en el centro del vector es menor que el elemento buscado, busca en la segunda mitad.
4. Se repiten los pasos hasta llegar al elemento que es buscado. En caso de no encontrarlo, el valor regresado es falso.

Aquí un muy breve video en donde se puede ver gráficamente lo que sucede cuando se ejecuta la búsqueda binaria, en dónde se busca el valor 17 en un vector de 40 valores.

Y aquí una liga para ver el código en C, en donde se aplica de forma recursiva: http://mygnet.net/codigos/c/metodos_de_busqueda/busqueda_binaria_de_forma_recursiva_sobre_un_vector_ordenado_dot_muy_completo.2936

Referencias:

http://www.programacionfacil.com/estructura_datos_csharp:busqueda_binaria