Complejidad del tiempo de búsqueda binaria

La búsqueda binaria es un paradigma de división y conquista. Busca un elemento en una matriz ordenada. En este artículo, solo se considera el ascendente. El elemento a buscar se llama valor objetivo. El valor objetivo puede o no encontrarse en la matriz.

La búsqueda comienza comparando el valor objetivo con el elemento medio de la matriz ordenada. Si el número de elementos en la matriz es uniforme, entonces el elemento a la mitad del número se considera el elemento central. Si el valor objetivo es el mismo que el elemento central, entonces se ha encontrado el índice de valor de destino. Si no son los mismos, entonces el valor objetivo es mayor o menor que el elemento medio. Si es más grande, la mitad inferior de la matriz será abandonada para que la búsqueda continúe en la mitad superior. Si es más pequeño, entonces la mitad superior de la matriz será abandonada, para que la búsqueda continúe en la mitad inferior.

La búsqueda continúa dividiendo la mitad elegida en dos nuevamente. Se realiza una comparación entre el valor objetivo y el elemento medio de esta nueva mitad. Si no son iguales, esta mitad se divide nuevamente en dos y por las mismas razones que se dividió la mitad anterior. Si el valor objetivo no es el mismo que el nuevo elemento central, entonces la división continúa.

Cuando el valor objetivo y un valor medio (ítem) son los mismos, eso es conquistador. Allí y luego, la búsqueda se detiene. Si el valor objetivo no está en la matriz, la búsqueda se detendrá en algún elemento medio final, que no es igual al valor de destino.

Este artículo tiene como objetivo dar una apreciación llamada complejidad del tiempo para la velocidad de la búsqueda binaria.

Contenido del artículo

• Introducción - Ver arriba
• Ilustración de búsqueda binaria
• Complejidad del tiempo y búsqueda binaria
• Codificación en C
• Conclusión

Ilustración de búsqueda binaria

Considere la lista ordenada:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Donde se debe buscar el entero, 3,. Por supuesto, la búsqueda desde el principio tomará tres operaciones. Sin embargo, el uso de la búsqueda binaria tomará cuatro operaciones principales de la siguiente manera:

El valor objetivo es 3. Dividir la lista en dos convierte a 8 el elemento central.

Es 8 igual que 3?

No. Dado que 3 es menos de 8, la búsqueda se centrará en la mitad inferior. Esa es una operación principal realizada.

Dividirse en dos nuevamente hace 4 el nuevo elemento central.

Es 4 igual que 3?

No. Dado que 3 es menos de 4, la búsqueda se centrará en la nueva mitad inferior. Esa es la segunda operación principal realizada.

Dividirse en dos nuevamente hace que 2 el nuevo elemento intermedio.

Es 2 igual que 3?

No. Dado que 3 es mayor que 2, la búsqueda se centrará en la nueva mitad superior. Esa es la tercera operación principal realizada.

Dividirse en dos nuevamente hace que 3 el nuevo elemento central, de una mitad (sublista) de longitud, uno. El artículo medio nuevo y último es ahora 3.

Es 3 lo mismo que 3?

Sí. Se ha encontrado el valor objetivo. Esa es la cuarta y última operación principal realizada.

Cuando hay 16 elementos, se puede hacer un máximo de 4 operaciones principales. Si hubiera 16 elementos, y el valor objetivo estaba en el rango y no se podía encontrar, 4 operaciones principales aún habrían tenido lugar. Por ejemplo, en la siguiente lista:

1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

Todavía hay 16 artículos. Un valor objetivo de 3 habría terminado con el valor de 5, con 4 operaciones principales.

Complejidad del tiempo y búsqueda binaria

El peor rendimiento de los casos

El rendimiento del peor de los casos se refiere al caso en el que el valor objetivo se encuentra en la última operación principal, o el valor objetivo está en el rango de valores y no se encuentra en la última operación principal.

Cuando el número de elementos es 16, el número máximo de operaciones siempre será 4.

16 = 2⁴
4 = registro₂(dieciséis)

Que sea N 16. Entonces,

4 = registro₂(norte)

Si n es 8, el número máximo de operaciones sería 3 = log₂(8). Si n es 32, el número máximo de operaciones sería 5 = log₂(32).

Se dice que la peor complejidad del tiempo (velocidad relativa) para la búsqueda binaria es:

O (registro₂(norte))

Donde el Big O y sus paréntesis tienen log₂(n) es la notación para la complejidad del tiempo. Simplemente se escribe como:

O (log n)

Mejor rendimiento

Suponga que el valor objetivo fue 8 para la primera lista anterior. En este caso, la primera operación principal habría encontrado la posición del valor objetivo. Este es el mejor rendimiento. La complejidad del tiempo para este mejor rendimiento se escribe como:

O (1)

Donde 1 significa una operación principal.

Codificación en C

Una función de búsqueda binaria de código C es:

#incluir
int binarySearch (int arr [], int Target, int n)
int loindex = 0;
int upIndex = n - 1;
// asegúrese de que todavía tengamos elementos en la lista para buscar en
while (lOindex Target)
upIndex = MiddleIndx;
demás
lOindex = MiddleIndx + 1;


// devuelve un número negativo cuando no podemos encontrar el objetivo en la matriz
regreso -1;

El lOindex significa el índice más bajo de una mitad (sublista). El upIndex significa el índice más alto de una mitad (sublist). Al principio, Loindex es 0 y UpIndex es 15 cuando n es 16. La condición del bucle mientras que la división continúe hasta que el lOindex sea lo mismo que upIndex si el valor objetivo aún no se ha encontrado.

Una función principal C adecuada para este código es:

int main (int argc, char ** argv)

int n = 16;
int Target = 3;
int arr [] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16;
int indexFound = binarySearch (arr, target, n);
printf ("%d \ n", indexFound);
regresar 0;

Conclusión

Este artículo discutió la complejidad del tiempo de búsqueda binaria y enfatizó lo siguiente:

La peor complejidad del tiempo para la búsqueda binaria es:
O (log n)

La mejor complejidad del tiempo para la búsqueda binaria es:
O (1)