Búsqueda binaria
Última actualización
La búsqueda binaria encuentra un valor objetivo en un arreglo **ordenado** reduciendo repetidamente la ventana de búsqueda a la mitad. Compara el elemento central con el objetivo: si coinciden, la búsqueda termina; si no, se descarta la mitad que no puede contener el objetivo y la ventana se reduce a la otra mitad. Cada comparación elimina la mitad de los elementos restantes, y por eso se ejecuta en O(log n): buscar entre un millón de valores ordenados requiere como máximo unas 20 comparaciones.
La animación de arriba muestra los punteros lo, mid y hi y atenúa la mitad eliminada tras cada comparación. La única precondición innegociable: el arreglo ya debe estar ordenado — con datos desordenados necesitas la búsqueda lineal o primero un ordenamiento (mira el merge sort). La misma idea de dividir a la mitad impulsa el árbol binario de búsqueda.
Complejidad temporal y espacial
| Caso | Complejidad | Notas |
|---|---|---|
| Mejor caso | O(1) | El elemento central es el objetivo en la primera comparación. |
| Caso promedio | O(log n) | Cada comparación reduce a la mitad la ventana restante. |
| Peor caso | O(log n) | La ventana se reduce a un solo elemento antes de acertar o fallar. |
| Espacio | O(1) | La versión iterativa solo guarda los índices lo, hi y mid. |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Asigna a lo el primer índice y a hi el último índice del arreglo ordenado. |
| 2 | Calcula el índice central: mid = (lo + hi) // 2. |
| 3 | Si a[mid] es igual al objetivo, devuelve mid — encontrado. |
| 4 | Si a[mid] es **menor** que el objetivo, este solo puede estar en la mitad derecha: asigna lo = mid + 1. |
| 5 | Si a[mid] es **mayor** que el objetivo, busca en la mitad izquierda: asigna hi = mid - 1. |
| 6 | Repite desde el paso 2 mientras lo <= hi; si la ventana se vacía, el objetivo no está en el arreglo. |
Ejemplo resuelto
Buscando 5 en [1, 2, 3, 5, 7, 8, 9]:
| Pasada | Ventana (lo..hi) | mid | a[mid] | Acción |
|---|---|---|---|---|
| 1 | [1, 2, 3, 5, 7, 8, 9] (0..6) | 3 | 5 | a[3] = 5 — objetivo encontrado en el índice 3. |
Un fallo, paso a paso
Buscar 4 en el mismo arreglo muestra cómo se vacía la ventana:
| Pasada | Ventana (lo..hi) | mid | a[mid] | Acción |
|---|---|---|---|---|
| 1 | 0..6 | 3 | 5 | 5 > 4 — busca en la mitad izquierda, hi = 2. |
| 2 | 0..2 | 1 | 2 | 2 < 4 — busca en la mitad derecha, lo = 2. |
| 3 | 2..2 | 2 | 3 | 3 < 4 — lo pasa a ser 3, la ventana se vacía: no encontrado. |
Cuándo usar la búsqueda binaria
| Úsala cuando | Evítala cuando |
|---|---|
| Los datos ya están ordenados (o los buscas muchas veces) | Los datos están desordenados y se buscan una sola vez — ordenar primero cuesta O(n log n) |
| La colección permite acceso aleatorio rápido (arreglos) | Solo tienes acceso secuencial (listas enlazadas) |
El conjunto de datos es grande — O(log n) brilla a gran escala | El conjunto de datos es diminuto — un recorrido simple es igual de rápido y más sencillo |
Código de Binary Search
Una implementación limpia y ejecutable de Binary Search en Python, JavaScript, Java, C++, C, Pseudocode. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Binary Search en Python
Python
1def binary_search(a, target):2 lo, hi = 0, len(a) - 13 while lo <= hi:4 mid = (lo + hi) // 25 if a[mid] == target:6 return mid7 if a[mid] < target:8 lo = mid + 1 # search the right half9 else:10 hi = mid - 1 # search the left half11 return -112
13
14nums = [1, 2, 3, 5, 7, 8, 9] # must be sorted15print("Index of 5:", binary_search(nums, 5))16print("Index of 4:", binary_search(nums, 4))Código de Binary Search en JavaScript
JavaScript
1function binarySearch(a, target) {2 let lo = 0;3 let hi = a.length - 1;4 while (lo <= hi) {5 const mid = Math.floor((lo + hi) / 2);6 if (a[mid] === target) return mid;7 if (a[mid] < target) {8 lo = mid + 1; // search the right half9 } else {10 hi = mid - 1; // search the left half11 }12 }13 return -1;14}15
16const nums = [1, 2, 3, 5, 7, 8, 9]; // must be sorted17console.log("Index of 5:", binarySearch(nums, 5));18console.log("Index of 4:", binarySearch(nums, 4));Código de Binary Search en Java
Java
1public class Main {2 static int binarySearch(int[] a, int target) {3 int lo = 0;4 int hi = a.length - 1;5 while (lo <= hi) {6 int mid = (lo + hi) / 2;7 if (a[mid] == target) return mid;8 if (a[mid] < target) {9 lo = mid + 1; // search the right half10 } else {11 hi = mid - 1; // search the left half12 }13 }14 return -1;15 }16
17 public static void main(String[] args) {18 int[] nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted19 System.out.println("Index of 5: " + binarySearch(nums, 5));20 System.out.println("Index of 4: " + binarySearch(nums, 4));21 }22}Código de Binary Search en C++
C++
1#include <iostream>2#include <vector>3
4int binarySearch(const std::vector<int>& a, int target) {5 int lo = 0;6 int hi = static_cast<int>(a.size()) - 1;7 while (lo <= hi) {8 int mid = lo + (hi - lo) / 2;9 if (a[mid] == target) return mid;10 if (a[mid] < target) {11 lo = mid + 1; // search the right half12 } else {13 hi = mid - 1; // search the left half14 }15 }16 return -1;17}18
19int main() {20 std::vector<int> nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted21 std::cout << "Index of 5: " << binarySearch(nums, 5) << "\n";22 std::cout << "Index of 4: " << binarySearch(nums, 4) << "\n";23 return 0;24}Código de Binary Search en C
C
1#include <stdio.h>2
3int binary_search(const int a[], int n, int target) {4 int lo = 0;5 int hi = n - 1;6 while (lo <= hi) {7 int mid = lo + (hi - lo) / 2;8 if (a[mid] == target) return mid;9 if (a[mid] < target) {10 lo = mid + 1; /* search the right half */11 } else {12 hi = mid - 1; /* search the left half */13 }14 }15 return -1;16}17
18int main(void) {19 int nums[] = {1, 2, 3, 5, 7, 8, 9}; /* must be sorted */20 int n = sizeof(nums) / sizeof(nums[0]);21 printf("Index of 5: %d\n", binary_search(nums, n, 5));22 printf("Index of 4: %d\n", binary_search(nums, n, 4));23 return 0;24}Código de Binary Search en Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74// The array must be sorted for binary search5nums[1] ← 16nums[2] ← 27nums[3] ← 38nums[4] ← 59nums[5] ← 710nums[6] ← 811nums[7] ← 912
13FUNCTION binarySearch(target : INTEGER) RETURNS INTEGER14 DECLARE lo : INTEGER15 DECLARE hi : INTEGER16 DECLARE mid : INTEGER17 lo ← 118 hi ← n19 WHILE lo <= hi DO20 mid ← (lo + hi) DIV 221 IF nums[mid] = target THEN22 RETURN mid23 ENDIF24 IF nums[mid] < target THEN25 // Target is larger — search the right half26 lo ← mid + 127 ELSE28 // Target is smaller — search the left half29 hi ← mid - 130 ENDIF31 ENDWHILE32 RETURN -133ENDFUNCTION34
35OUTPUT "Index of 5 is ", binarySearch(5)36OUTPUT "Index of 4 is ", binarySearch(4)Preguntas frecuentes sobre la búsqueda binaria
¿Cuál es la complejidad temporal de la búsqueda binaria?
O(log n) en los casos promedio y peor, porque cada comparación reduce a la mitad la ventana de búsqueda restante, y O(1) en el mejor caso, cuando el primer elemento central es el objetivo. La versión iterativa usa O(1) de espacio adicional.¿Por qué la búsqueda binaria requiere un arreglo ordenado?
El paso de dividir a la mitad depende del orden: comparar el objetivo con el elemento central solo te dice qué mitad descartar si todo lo que está a la izquierda del centro es menor y todo lo que está a la derecha es mayor. Con datos desordenados esa inferencia no es válida — usa la búsqueda lineal en su lugar, u ordena primero.
¿Cuál es la diferencia entre la búsqueda binaria y la búsqueda lineal?
La búsqueda lineal recorre los elementos uno por uno (
O(n)) y funciona con cualquier arreglo; la búsqueda binaria divide a la mitad la ventana de búsqueda de un arreglo ordenado (O(log n)), pero requiere una entrada ordenada. Para un puñado de elementos la diferencia es insignificante — a gran escala la búsqueda binaria gana de forma contundente.¿Cuántas comparaciones necesita la búsqueda binaria?
Como máximo unas
log2(n) + 1: 10 comparaciones cubren 1,000 elementos, 20 comparaciones cubren 1,000,000. Ese crecimiento logarítmico es lo que la convierte en la búsqueda por defecto sobre datos ordenados.¿Cuál es el clásico error de desbordamiento en la búsqueda binaria?
Calcular el centro como
(lo + hi) / 2 puede desbordar los enteros de tamaño fijo cuando lo + hi supera el máximo del tipo. La forma segura es mid = lo + (hi - lo) / 2. En Python no importa (enteros de precisión arbitraria), pero en Java/C/C++ es un error real y famoso.¿La búsqueda binaria es lo mismo que un árbol binario de búsqueda?
Comparten la idea de dividir a la mitad, pero difieren en estructura: la búsqueda binaria es un algoritmo sobre un arreglo ordenado, mientras que un árbol binario de búsqueda es una estructura de datos enlazada que mantiene sus claves ordenadas para que las búsquedas desciendan a la izquierda o a la derecha en cada nodo.
Recursos relacionados
Más visualizaciones
