BÚSQUEDA BINARIA


BÚSQUEDA BINARIA

Si los elementos sobre los que se realiza la búsqueda están ordenados, entonces podemos utilizar un algoritmo de búsqueda mucho más rápido que el secuencial: la búsqueda binaria. Consiste en reducir en cada paso el ámbito de búsqueda a la mitad de los elementos, basándose en comparar el elemento a buscar con el elemento que se encuentra en la mitad del intervalo y con base en esta comparación:
·        
  •       Si el elemento buscado es menor que el elemento medio, entonces sabemos que elemento está en la mitad inferior de la tabla.
  •           Si es mayor es porque el elemento está en la mitad superior.
  •        Si es igual se finaliza con éxito la búsqueda ya que se ha encontrado el elemento.

Si se vuelve a repetir el mismo proceso anterior con la parte del arreglo que no hemos descartado, iremos avanzando rápidamente hacia el valor que queremos localizar. Puede darse el caso en el que el sub-arreglo a dividir está vacío y aún no se ha encontrado el elemento. Sobre entendemos que el valor buscado no existe en el arreglo.

Comentarios

Publicar un comentario

Entradas más populares de este blog

MÉTODO DE BINSORT

              MÉTODO DE BINSORT Este método, también llamado clasificación por urnas, persigue conseguir funciones de tiempo de ejecución menores de O(n log n), para ordenar una secuencia de n elementos siempre que se conozca algo acerca del tipo de las claves por las que se están ordenando. Supóngase que se tiene un vector v[] de registros, se quiere ordenar respecto un campo clave de tipo entero, además se sabe que los valores de las claves se encuentran en el rango de 1 a n, sin claves duplicadas y siendo n el número de elementos. En estas circunstancias es posible colocar los registros ordenados en un array auxiliar t[] mediante este bucle: for 1:= 1 to n do        t[v[i].clave] = v[i]; Sencillamente determina la posición que le corresponde según el valor del campo clave. El bucle lleva un tiempo de ejecución de complejidad O(n). Esta ordenación tan sencilla que se ha expuesto es un caso particular del método de ordenación por urnas (binsort). Este método
Leer más