Complejidad del tiempo de Búsqueda binaria es O(log n) , dónde norte es el número de elementos de la matriz. Divide la matriz por la mitad en cada paso. Complejidad espacial es O(1) ya que utiliza una cantidad constante de espacio extra.

sistemas operativos mac

Ejemplo de algoritmo de búsqueda binaria

Las complejidades temporales y espaciales del algoritmo de búsqueda binaria se mencionan a continuación.

Complejidad temporal de Algoritmo de búsqueda binaria :

Mejor complejidad temporal del algoritmo de búsqueda binaria: O(1)

El mejor caso es cuando el elemento está en el índice medio de la matriz. Sólo se necesita una comparación para encontrar el elemento objetivo. Entonces, la complejidad del mejor de los casos es O(1) .

Complejidad de tiempo promedio de caso del algoritmo de búsqueda binaria: O(logN)

Considere la matriz llegar[] de longitud norte y elemento X para ser encontrado. Pueden darse dos casos:

• Caso 1: El elemento está presente en la matriz.
• Caso2: El elemento no está presente en la matriz.

Hay norte Caso1 y 1 Caso2. Entonces número total de casos = N+1 . Ahora observe lo siguiente:

• Un elemento en el índice N/2 se puede encontrar en 1 comparación
• Los elementos del índice N/4 y 3N/4 se pueden encontrar en 2 comparaciones.
• Los elementos con índices N/8, 3N/8, 5N/8 y 7N/8 se pueden encontrar en 3 comparaciones, etc.

En base a esto podemos concluir que elementos que requieren:

• 1 comparación = 1
• 2 comparaciones = 2
• 3 comparaciones = 4
• X comparaciones = 2 ^x-1 dónde X pertenece al rango [1, iniciar sesiónN] porque comparaciones máximas = tiempo máximo que N se puede reducir a la mitad = comparaciones máximas para alcanzar el 1er elemento = logN.

Entonces, comparaciones totales
= 1*(elementos que requieren 1 comparación) + 2*(elementos que requieren 2 comparaciones) + . . . + logN*(elementos que requieren comparaciones logN)
= 1*1 + 2*2 + 3*4 + . . . + logN * (2^registroN-1)
= 2^calma* (logN – 1) + 1
= norte * (lognorte – 1) + 1

c booleano

Número total de casos = N+1 .

fcfs

Por lo tanto, la complejidad promedio = ( N*(logN – 1) + 1)/N+1 = N*logN / (N+1) + 1/(N+1) . Aquí el término dominante es N*logN/(N+1) que es aproximadamente calma . Entonces la complejidad promedio del caso es O(logN)

Peor caso de complejidad temporal del algoritmo de búsqueda binaria: O(logN)

El peor caso será cuando el elemento esté presente en la primera posición. Como se ve en el caso promedio, la comparación requerida para llegar al primer elemento es calma . Entonces la complejidad temporal para el peor de los casos es O(logN) .

Complejidad espacial auxiliar del algoritmo de búsqueda binaria

El complejidad del espacio auxiliar del Algoritmo de búsqueda binaria es O(1) , lo que significa que requiere una cantidad constante de espacio adicional independientemente del tamaño de la matriz de entrada. Esto se debe a que la búsqueda binaria es un algoritmo iterativo que no requiere estructuras de datos adicionales ni recursividad que crece con el tamaño de entrada. Aunque también podemos implementar la búsqueda binaria de forma recursiva.