DAA - Búsqueda binaria

En este capítulo, discutiremos otro algoritmo basado en el método de divide y vencerás.

Planteamiento del problema

La búsqueda binaria se puede realizar en una matriz ordenada. En este enfoque, el índice de un elementoxse determina si el elemento pertenece a la lista de elementos. Si la matriz no está ordenada, se utiliza la búsqueda lineal para determinar la posición.

Solución

En este algoritmo, queremos encontrar si el elemento x pertenece a un conjunto de números almacenados en una matriz numbers[]. Dóndel y r representan el índice izquierdo y derecho de una submatriz en la que se debe realizar la operación de búsqueda.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

Análisis

La búsqueda lineal se ejecuta en O(n)hora. Mientras que la búsqueda binaria produce el resultado enO(log n) hora

Dejar T(n) ser el número de comparaciones en el peor de los casos en una matriz de n elementos.

Por lo tanto,

$$ T (n) = \ begin {cases} 0 & if \: n = 1 \\ T (\ frac {n} {2}) + 1 & de lo contrario \ end {cases} $$

Usando esta relación de recurrencia $ T (n) = log \: n $.

Por lo tanto, la búsqueda binaria usa $ O (log \: n) $ time.

Ejemplo

En este ejemplo, buscaremos el elemento 63.