Búsqueda binaria

1. Algoritmo de búsqueda binaria
2. Ejemplo de búsqueda binaria
3. Implementación del algoritmo de búsqueda binaria
4. Complejidad del algoritmo de búsqueda binaria

La búsqueda binaria es el algoritmo de búsqueda más popular y eficiente. De hecho, es el algoritmo de búsqueda más rápido. Al igual que la ordenación por salto, también necesita que se ordene el array. Se basa en el enfoque de dividir y conquistar en el que dividimos el array en dos mitades y luego comparamos el elemento que estamos buscando con el elemento del medio. Si el elemento del medio coincide, devolvemos el índice del elemento del medio; de lo contrario, nos movemos a la mitad izquierda y derecha según el valor del artículo.

Algoritmo de búsqueda binaria

Supongamos que tenemos un array sin clasificar A[] que contiene n elementos, y queremos encontrar un elemento X.

Ejemplo de búsqueda binaria

Supongamos que tenemos el array: (1, 2, 3, 4, 5, 6, 7, 8, 9), y queremos encontrar X - 8.

Implementación del algoritmo de búsqueda binaria

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int lo, int hi, int x) {
  while (lo <= hi) {
    int m = lo + (hi - lo) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      lo = m + 1;
    else
      hi = m - 1;
  }
  return -1;
}

int main(void) {
  int n = 9;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 8;
  int result = binarySearch(arr, 0, n - 1, x);
  if (result == -1) {
    cout << "Element not found !!";
  } else
    cout << "Element found at index " << result;
  return 0;
}

Complejidad del algoritmo de búsqueda binaria

Complejidad del tiempo

• Caso promedio

Cuando realizamos la búsqueda binaria, buscamos en una mitad y descartamos la otra mitad, reduciendo el tamaño del array a la mitad cada vez.

La expresión para la complejidad del tiempo viene dada por la recurrencia.

T(n) = T(n/2) + k , k is a constant.

Este resultado de esta recurrencia da logn, y la complejidad temporal es del orden de O(logn). Es más rápido que la búsqueda lineal y la búsqueda por salto.

• Mejor caso

El mejor de los casos ocurre cuando el elemento del medio es el elemento que estamos buscando y se devuelve en la primera iteración. La complejidad del tiempo en el mejor de los casos es O(1).

• Peor caso

La complejidad del tiempo del caso más desfavorable es la misma que la complejidad del tiempo del caso medio. La complejidad de tiempo en el peor de los casos es O(logn).

Complejidad espacial

La complejidad espacial de este algoritmo es O(1) en el caso de implementación iterativa porque no requiere ninguna estructura de datos más que variables temporales.

En el caso de la implementación recursiva, la complejidad del espacio es O(logn) debido al espacio requerido por la pila de llamadas recursivas.