domingo, 12 de septiembre de 2010

Busqueda Binaria

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.
Para complemetar un ejemplo de mi compañero Roberto