arrays - iterativa - busqueda binaria pdf

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

Question

Hola, aquí abajo está el pseudo código para mi implementación de búsqueda binaria:

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 que haría esta implementación en el peor de los casos para una matriz ordenada de tamaño n?

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

Answer 1

De acuerdo con la página de wikipedia en la búsqueda binaria , el peor desempeño de este algoritmo es O(lg n) , que mide el número asintótico de comparaciones necesarias. El número de comparaciones en el peor de los casos sería 2*lg(n-1) , como se ha señalado 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 esperadas se mantienen para una matriz (o vector) de tamaño n :

• Mejor rendimiento de caso: O(1)
• Rendimiento promedio del caso: O(lg n)
• El peor desempeño de 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 . Todavía no puedes regresar
• La línea: m ← floor((l+r)/2) puede causar un desbordamiento si los números son lo suficientemente grandes cuando se trabaja con números enteros de tamaño fijo. La sintaxis correcta varía según el lenguaje de programación real que esté utilizando, pero algo así solucionará el problema: m ← (l + r) >>> 1 , donde >>> es el operador de cambio a la derecha sin signo. Lea más sobre el problema here .

Answer 2

El caso más desfavorable en este caso es si el elemento K no está presente en A y es más pequeño que todos los elementos en A. Luego, tenemos dos comparaciones en cada paso: K > A[m] y K < A[m] .

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

Esto lleva a un total de 2*log_2(n-1) comparaciones, que en realidad son asintóticamente iguales a O(log(n)) .

Answer 3

Una corrección muy pequeña a la respuesta de Hielsnoppe :

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

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

Entonces, si denotamos el número máximo (en el peor de los casos) de comparaciones para una búsqueda en una matriz de n -elementos por C(n) , tenemos

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

Para n = 2k+1 impar n = 2k+1 , el piso y el techo son idénticos, por lo que el máximo es evidentemente el último,

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

y para n = 2k , encontramos

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

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

Evaluando 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í que por inducción probamos

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)))).

Este es un límite superior exacto.