La búsqueda binaria es una — su estimación de complejidad es O(log2(n)), mientras que la búsqueda secuencial convencional tiene O(n). Esto significa que, por ejemplo, para una matriz de 1024 elementos, una búsqueda lineal, en el peor de los casos, cuando el elemento deseado no está en la matriz, procesará los 1024 elementos. La búsqueda binaria es suficiente para procesar elementos \(log_2(1024) = 10\). Este resultado se logra debido al hecho de que después del primer paso del bucle, el área de búsqueda se reduce a 512 elementos, después del segundo – hasta 256 etc.
Las desventajas de este algoritmo son el requisito de ordenar los datos, así como la capacidad de acceder a cualquier elemento de datos en un tiempo constante (independientemente de la cantidad de datos). Por lo tanto, el algoritmo no puede funcionar en matrices no ordenadas ni en ninguna estructura de datos basada en listas vinculadas.
Implementación
adiós (derecha – izquierda > 1) // Siempre que el borde derecho esté a la derecha de la izquierda
nc
medio = (izquierda + derecha) /< /span> 2; // Medio del área de búsqueda
si (A[medio] >= b) entonces
derecha = medio; // Mover el borde derecho
de lo contrario
izquierda = medio; // De lo contrario, mueva el borde izquierdo
cc
si (A[derecha] == X) entonces
salida derecha;
de lo contrario
salida -1;
donde:
A - matriz fuente,
N - tamaño de matriz,
X - el número deseado.
|