Binary Search

Binary Search (búsqueda binaria) es un algoritmo para buscar un valor en una lista ordenada. Usa la idea divide y vencerás: cada comparación elimina la mitad de los elementos restantes, por eso es muy rápido (tiempo $O(\log n)$).

Requisito imprescindible: la lista tiene que estar ordenada (por ejemplo, de menor a mayor).

Algoritmo

1. Mantienes dos índices: low (inicio) y high (fin).
2. Calculas el punto medio mid.
3. Comparas lista[mid] con el valor buscado x:
   • si lista[mid] == x → lo encontraste;
   • si lista[mid] < x → el valor, si existe, está en la mitad derecha → actualizas low = mid + 1;
   • si lista[mid] > x → está en la mitad izquierda → high = mid - 1.
4. Repetir hasta encontrarlo o hasta que low > high (no existe).

Paso a paso con un ejemplo

Lista ordenada

[2, 5, 7, 12, 16, 23, 38, 56, 72, 91]

Buscamos 23.

• Inicial: low = 0, high = 9.
• Iteración 1:
  • mid = 0 + (9-0)//2 = 4 → lista[4] = 16
  • 16 < 23 → descartamos izquierda → low = 5, high = 9.
• Iteración 2:
  • mid = 5 + (9-5)//2 = 7 → lista[7] = 56
  • 56 > 23 → descartamos derecha → low = 5, high = 6.
• Iteración 3:
  • mid = 5 + (6-5)//2 = 5 → lista[5] = 23
  • 23 == 23 → ¡encontrado en índice 5!

Si hubiéramos buscado 20:

• tras unos pasos acabaríamos con low > high → concluimos “no encontrado”.

Variantes y notas importantes

• Complejidad: tiempo $O(\log n)$, espacio $O(1)$ en la versión iterativa. La versión recursiva usa $O(\log n)$ stack.
• Duplicados: si hay varios elementos iguales, la búsqueda estándar puede devolver cualquiera de ellos; para la primera o última ocurrencia hay pequeñas modificaciones (buscar siempre hacia la izquierda/derecha cuando haya igualdad).
• Estructura: necesita acceso por índice (arrays, listas con acceso aleatorio). En listas enlazadas no es buena idea porque acceder al medio no es $O(1)$.