¿Cuántas comparaciones hará la búsqueda binaria en el peor de los casos utilizando este algoritmo?

Question

Hola a continuación es el pseudo código binario para mi aplicación de búsqueda:

Input: (A[0...n-1], K) 
begin 
    l ← 0; r ← n-1 
    while l ≤ r do 
     m ← floor((l+r)/2) 
     if K > A[m] then l ← m+1 
     else if K < A[m] then r ← m-1 else return m 
     end if 
    end while 
    return -1 // key not found 
end 

Me preguntaba cómo calcular el número de comparaciones esta aplicación sería en el peor de los casos para un arreglo ordenado de tamaño n?

¿El número de comparaciones = lg n + 1? o algo diferente?

Answer 1

El peor de los casos en este caso, es decir, si el elemento K no está presente en A y menor que todos los elementos de A. Entonces tenemos dos comparaciones en cada paso: K > A[m] y K < A[m].

En cada paso, la matriz se corta en dos partes, cada una del tamaño (n-1)/2, tenemos un máximo de log_2(n-1) pasos.

Esto lleva a un total de 2*log_2(n-1) comparaciones, que asintóticamente es igual a O(log(n)).

Answer 2

De acuerdo con la página de wikipedia en binary search, el peor rendimiento de este algoritmo es O(lg n), que mide el número asintótico de comparaciones necesarias. El real el peor número de comparaciones sería 2*lg(n-1), como se señaló en la respuesta de @ hielsnoppe.

El pseudocódigo en la pregunta representa la implementación típica de una búsqueda binaria, por lo que las complejidades de rendimiento esperados mantener durante un array (o vector) de tamaño n:

• mejor rendimiento caso: O(1)
• media rendimiento caso: O(lg n)
• peor rendimiento caso: O(lg n)

En una inspección más cercana, hay dos problemas con el pseudocódigo en la pregunta:

• La línea: if K > A[m] then return l ← m+1 debe leer if K > A[m] then l ← m+1. No puede volver todavía
• La línea: m ← floor((l+r)/2) puede causar un desbordamiento si los números son lo suficientemente grandes cuando se trabaja con enteros de tamaño fijo. La sintaxis correcta varía según el lenguaje de programación real que esté utilizando, pero algo a lo largo de esto solucionará el problema: m ← (l + r) >>> 1, donde >>> es el operador de desplazamiento a la derecha sin signo. Lea más sobre el problema en here.

Answer 3

una corrección muy menor a hielsnoppe's answer:

En una serie -elemento n (n > 0), el elemento de comparar está en el índice m = floor((n-1)/2). Así que hay tres posibilidades

1. A[m] < K, a continuación, después de una comparación, la búsqueda continúa en una serie n-1-m = ceiling((n-1)/2) -elemento.
2. A[m] > K, luego de dos comparaciones, la búsqueda continúa en una matriz de elementos m.
3. A[m] == K, luego hemos terminado después de dos comparaciones.

Así que si denotamos la máxima (peor caso) número de comparaciones para una búsqueda en una variedad n -elemento por C(n), tenemos

C(0) = 0 
C(n) = max { 1 + C(ceiling((n-1)/2), 2 + C(floor((n-1)/2) }, n > 0 

Por extraño n = 2k+1, el suelo y el techo son idénticos, por lo que el máximo es evidente que este último,

C(2k+1) = 2 + C(k) 

e incluso por n = 2k, encontramos

C(2k) = max { 1 + C(k), 2 + C(k-1) }. 

Para n = 2, que se resuelve a C(2) = 1 + C(1) = 1 + 2 = 3, para todos, incluso más grande n, el máximo es 2 + C(k-1), ya que para n >= 1 tenemos C(n) <= C(n+1) <= C(n) + 1.

Evaluación de la recursividad para los primeros n, encontramos

C(0) = 0 
C(1) = 2 
C(2) = 3 
C(3) = C(4) = 4 
C(5) = C(6) = 5 
C(7) = C(8) = C(9) = C(10) = 6 
C(11) = ... = C(14) = 7 
C(15) = ... = C(22) = 8 
C(23) = ... = C(30) = 9 

Así por inducción se prueba

C(n) = 2k, if 2^k <= n+1 < 2k + 2^(k-1), and 
C(n) = 2k+1, if 2^k + 2^(k-1) <= n+1 < 2^(k+1) 

o

C(n) = 2*log2(n+1) + floor(2*(n+1)/(3*2^floor(log2(n+1)))). 

Ésta es una cota superior exacta.