Búsqueda binaria
La búsqueda binaria descarta media zona tras cada comparación.
¿Qué es Búsqueda binaria?
La búsqueda binaria descarta media zona tras cada comparación.
Busca datos ordenados en tiempo logarítmico.
Puntos importantes
- Prueba entradas vacías, únicas, duplicadas y ordenadas.
- Separa corrección y optimización.
- Prefiere la biblioteca estándar en producción.
Visualizador de Búsqueda binaria
O(log n)Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.
Ejemplos de código C y C++
main.c
#include <stdio.h>
int search(const int *values, int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
int middle = low + (high - low) / 2;
if (values[middle] == target) return middle;
if (values[middle] < target) low = middle + 1;
else high = middle - 1;
}
return -1;
}
int main(void) {
int values[] = {3, 7, 11, 16, 23, 28};
printf("index=%d\n", search(values, 6, 23));
}
index=4C++
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector values{3, 7, 11, 16, 23, 28};
auto match = std::lower_bound(values.begin(), values.end(), 23);
std::cout << "index="
<< std::distance(values.begin(), match) << '\n';
}
index=4Comparación entre C y C++
La entrada debe estar ordenada. El bucle C y std::lower_bound son O(log n) sobre acceso aleatorio.
C
Bucles, punteros, tamaños y buffers se escriben explícitamente.
C++
Iteradores y algoritmos separan la operación del almacenamiento.
Ejercicios prácticos
Ejecuta ambas versiones y modifícalas para observar sus garantías.
- Traza cada comparación.
- Prueba duplicados y valores extremos.
- Compara con la biblioteca estándar.