Estructura de datos y algoritmos Búsqueda binaria

La búsqueda binaria es un algoritmo de búsqueda rápida con una complejidad en tiempo de ejecución de Ο (log n). Este algoritmo de búsqueda funciona según el principio de divide y vencerás. Para que este algoritmo funcione correctamente, la recopilación de datos debe estar ordenada.

La búsqueda binaria busca un elemento en particular comparando el elemento más intermedio de la colección. Si se produce una coincidencia, se devuelve el índice del elemento. Si el elemento del medio es mayor que el elemento, entonces el elemento se busca en la submatriz a la izquierda del elemento del medio. De lo contrario, el elemento se busca en la submatriz a la derecha del elemento del medio. Este proceso continúa en el subarreglo también hasta que el tamaño del subarreglo se reduce a cero.

¿Cómo funciona la búsqueda binaria?

Para que una búsqueda binaria funcione, es obligatorio que la matriz de destino esté ordenada. Aprenderemos el proceso de búsqueda binaria con un ejemplo pictórico. La siguiente es nuestra matriz ordenada y supongamos que necesitamos buscar la ubicación del valor 31 usando una búsqueda binaria.

Primero, determinaremos la mitad de la matriz usando esta fórmula:

mid = low + (high - low) / 2

Aquí está, 0 + (9-0) / 2 = 4 (valor entero de 4.5). Entonces, 4 es la mitad de la matriz.

Ahora comparamos el valor almacenado en la ubicación 4, con el valor que se busca, es decir, 31. Encontramos que el valor en la ubicación 4 es 27, que no coincide. Como el valor es mayor que 27 y tenemos una matriz ordenada, también sabemos que el valor objetivo debe estar en la parte superior de la matriz.

Cambiamos nuestro valor bajo a medio + 1 y volvemos a encontrar el nuevo valor medio.

low = mid + 1
mid = low + (high - low) / 2

Nuestro nuevo mid es 7 ahora. Comparamos el valor almacenado en la ubicación 7 con nuestro valor objetivo 31.

El valor almacenado en la ubicación 7 no coincide, más bien es más de lo que estamos buscando. Entonces, el valor debe estar en la parte inferior de esta ubicación.

Por lo tanto, calculamos el medio nuevamente. Esta vez son las 5.

Comparamos el valor almacenado en la ubicación 5 con nuestro valor objetivo. Descubrimos que es una coincidencia.

Concluimos que el valor objetivo 31 se almacena en la ubicación 5.

La búsqueda binaria divide a la mitad los elementos que se pueden buscar y, por lo tanto, reduce el recuento de comparaciones a realizar a muy menos números.

Pseudocódigo

El pseudocódigo de los algoritmos de búsqueda binaria debería verse así:

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Para conocer la implementación de la búsqueda binaria usando array en el lenguaje de programación C, haga clic aquí .