¿Cuántas comparaciones hará la búsqueda binaria en el peor de los casos usando este algoritmo?
Hola, aquí abajo está el pseudo código para mi implementación de búsqueda binaria:
<code>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 </code>
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?