TOP

Búsqueda Binaria Iteractiva

Publicado por Unknown en 21:35

BUENAS TARDES COMPAÑEROS

 EL TEMA DE HOY ES BUSQUEDAD BINARIA INTERACTIVA.
BUSQUEDAD BINARIA
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 exponencialmente 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).

                                    EXPLICACIÓN


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
A continuación se presenta el  algoritmo en PSeint, 




Este es el cogido principal del algoritmo o el que realiza la busquedad por medio de comparaciones.

como lo realiza: 
primero a la variable centro le damos el valor de la mitad del vector y la comparamos con el numero ingresado y si es igual el programa termina, sino lo que hace es comparar si el numero ingresado es mayor o menor que el centro, y si es mayor lo compara con los números mayor que el centro y sigue dividiendo el vector hasta que encuentre el numero o no en el vector, al igual cuando es menor que el centro hace el mismo procedimiento.

DIAPOSITIVAS 


2 comentarios:

  1. 14 de marzo de 2013, 13:36

    Excelente tu aporte, me pareció un tema muy interesante. Faltaría el vídeo para que quede aun mas claro. Gracias

  2. never
    19 de mayo de 2016, 13:56

    gracias por este gran aporte

Publicar un comentario