Búsqueda Binaria
|
Se llama tambien dicotonámica. Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponenciamente el número de iteraciones necesarias. Está
altamente recomendado para buscar en arrays de gran
tamaño. Por ejemplo, en uno conteniendo 50.000.000
elementos, realiza como máximo 26 comparaciones (en el
peor de los casos).
Para
implementar este algoritmo se compara el elemento a
buscar con un elemento cualquiera del array
(normalmente el elemento central): si el valor de éste
es mayor que el del elemento buscado se repite el
procedimiento en la parte del array que va desde el
inicio de éste hasta el elemento tomado, en caso
contrario se toma la parte del array que va desde el
elemento tomado hasta el final. De esta manera
obtenemos intervalos cada vez más pequeños, hasta que
se obtenga un intervalo indivisible. Si el elemento no
se encuentra dentro de este último entonces se deduce
que el elemento buscado no se encuentra en todo el
array.
A
continuación se presenta el pseudocódigo del
algoritmo, tomando como elemento inicial el elemento
central del array.
Datos
de entrada:
vec: vector en el que se desea buscar el dato
tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive. dato: elemento que se quiere buscar. Variables centro: subíndice central del intervalo inf: límite inferior del intervalo sup: límite superior del intervalo inf = 0 sup = tam-1 Mientras inf <= sup: centro = ((sup - inf) / 2) + inf // División entera: se trunca la fracción Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario: Si dato < vec[centro] entonces: sup = centro - 1 En caso contrario: inf = centro + 1 Fin (Mientras) Devolver Falso
|