Búsqueda binaria: 8 ejercicios resueltos
Practica búsqueda binaria con 8 ejercicios resueltos: trazas, índices, duplicados, límites de inserción, recuentos y el requisito de una lista ordenada.
Estos ejercicios de búsqueda binaria trabajan algo más que dividir una lista por la mitad: hay que seguir un código concreto, respetar sus límites y reconocer qué significa su resultado. Una posición encontrada, la primera aparición y un punto de inserción no son la misma respuesta.
Son ocho ejercicios originales con cuatro alternativas y soluciones explicadas. Los bloques Python de esta página se han ejecutado con Python 3.14.3 y sus resultados se han contrastado con comprobaciones lineales. No son preguntas oficiales ni una medición de rendimiento.
Convenciones y dos contratos
Todos los índices empiezan en cero. Salvo el contraejemplo explícito del caso 8, las listas están ordenadas de menor a mayor, admitiendo duplicados, y no cambian durante la llamada. Los elementos y valores buscados son enteros.
Llamamos sondeo a una iteración que consulta a[medio]. No contamos instrucciones ni comparaciones individuales: una iteración puede evaluar primero igualdad y después una desigualdad. Las trazas se refieren a los códigos mostrados, no a cualquier implementación de búsqueda binaria.
Buscar una coincidencia: intervalo cerrado
Esta función devuelve un índice que contiene x o -1 si no encuentra coincidencia. No garantiza la primera aparición de un duplicado. El intervalo candidato es [izq, der], con ambos extremos incluidos.
def buscar(a, x):
izq, der = 0, len(a) - 1
while izq <= der:
medio = (izq + der) // 2
if a[medio] == x:
return medio
if a[medio] < x:
izq = medio + 1
else:
der = medio - 1
return -1Límite izquierdo: intervalo semiabierto
Esta otra función devuelve la primera frontera que deja a su izquierda únicamente valores menores que x. El intervalo de búsqueda es [izq, der): der queda excluido y empieza en len(a).
def limite_izquierdo(a, x):
izq, der = 0, len(a)
while izq < der:
medio = (izq + der) // 2
if a[medio] < x:
izq = medio + 1
else:
der = medio
return izqUna igualdad se trata de manera distinta en cada función. No mezcles el der = medio de la segunda con las actualizaciones de la primera. En la segunda, devolver len(a) es válido como frontera de inserción, pero no permite indexar un elemento existente en esa posición.
La documentación de bisect de Python 3.14 define sus fronteras izquierda y derecha. También se ha consultado el código fuente de CPython 3.14.3. Las preguntas y los dos códigos didácticos anteriores son propios. La documentación web consultada corresponde a la rama 3.14; la versión ejecutada en estas pruebas es 3.14.3.
Ejercicio 1. Localizar un valor
Aplica buscar a a = [4, 9, 13, 18, 26, 31, 40], con x = 26. ¿Qué índice devuelve y cuántos sondeos realiza?
A. Índice 4 y 3 sondeos.
B. Índice 5 y 3 sondeos.
C. Índice 4 y 2 sondeos.
D. Índice 26 y 1 sondeo.
Ver solución del ejercicio 1
Correcta: A. Devuelve 4 tras 3 sondeos. Los límites de la tabla son los que hay al comenzar cada iteración:
| Sondeo | izq | der | medio | a[medio] |
|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 18 |
| 2 | 4 | 6 | 5 | 31 |
| 3 | 4 | 4 | 4 | 26 |
Al ver 18 se descarta hasta el índice 3; al ver 31 se descarta desde el 5. El siguiente valor coincide. El índice 4 es la quinta posición cuando cuentas desde uno. El 26 es el valor encontrado, no un índice.
Ejercicio 2. La búsqueda termina sin encontrar
Aplica buscar a a = [3, 8, 12, 19, 25, 33], con x = 17. ¿Qué devuelve y cuáles son izq y der al terminar?
A. Devuelve 3; izq = 3; der = 3.
B. Devuelve -1; izq = 2; der = 3.
C. Devuelve 17; izq = 3; der = 2.
D. Devuelve -1; izq = 3; der = 2.
Ver solución del ejercicio 2
Correcta: D. Devuelve -1, con izq = 3 y der = 2. Los índices medios son 2, 4 y 3; sus valores son 12, 25 y 19. Después del último sondeo se asigna der = 3 - 1 = 2, mientras izq sigue en 3.
El intervalo cerrado ha quedado vacío porque izq supera a der. El índice 3 sería el punto donde insertar 17 para mantener el orden, pero esta función no devuelve puntos de inserción: su contrato es encontrar una igualdad o devolver -1. Tampoco devuelve el propio valor buscado si no aparece.
Ejercicio 3. Coincidir no equivale a encontrar el primero
Aplica buscar a a = [1, 4, 7, 7, 7, 10, 14], con x = 7. ¿Qué índice devuelve este código concreto?
A. 2.
B. 3.
C. 4.
D. 7.
Ver solución del ejercicio 3
Correcta: B. Devuelve 3. El primer punto medio es (0 + 6) // 2 = 3 y a[3] ya vale 7. La función retorna en esa primera igualdad, sin seguir buscando a la izquierda.
La primera aparición está en el índice 2, pero encontrar alguna aparición y localizar la primera son contratos distintos. El índice 4 también contiene 7, aunque este código no llega a él. El 7 es el valor, no una posición válida en esta lista de siete elementos.
Ejercicio 4. Localizar el límite izquierdo
Aplica limite_izquierdo a a = [2, 6, 6, 6, 11, 15], con x = 6. ¿Qué índice devuelve?
A. 0.
B. 3.
C. 1.
D. 6.
Ver solución del ejercicio 4
Correcta: C. Devuelve 1, la frontera que deja a su izquierda los valores menores que 6. Los índices medios son 3, 1 y 0. En las dos igualdades se mueve der al medio; después, al encontrar 2, izq avanza a 1 y el intervalo queda vacío.
El cambio respecto a buscar es deliberado: una igualdad no retorna inmediatamente. Conserva la posibilidad de que haya otra aparición anterior. Este contrato coincide con el de bisect_left para los enteros ordenados de esta práctica. Un límite izquierdo puede ser un punto de inserción aunque x no aparezca.
Ejercicio 5. Contar duplicados con dos fronteras
En a = [2, 5, 5, 5, 9, 9, 12], con x = 9, se calcula bisect_right(a, x) - bisect_left(a, x). ¿Cuántas apariciones devuelve?
A. 4.
B. 6.
C. 2.
D. 3.
Ver solución del ejercicio 5
Correcta: C. Devuelve 2. El límite izquierdo es 4 y el derecho 6. Las apariciones ocupan los índices 4 y 5: el intervalo [4, 6) tiene longitud dos.
from bisect import bisect_left, bisect_right
a = [2, 5, 5, 5, 9, 9, 12]
x = 9
cantidad = bisect_right(a, x) - bisect_left(a, x)El 4 y el 6 son fronteras, no recuentos. No sumes uno a la diferencia: el límite derecho ya está situado después de las coincidencias. Las listas deben conservar el orden exigido por estas funciones.
Ejercicio 6. El punto de inserción puede quedar fuera de los índices
En a = [3, 7, 12, 18], con x = 21, se calcula bisect_left(a, x). ¿Qué posición devuelve?
A. 4.
B. 3.
C. -1.
D. 21.
Ver solución del ejercicio 6
Correcta: A. Devuelve 4, que coincide con len(a). Es el lugar de inserción al final, pero no es un índice de un elemento que ya exista: los índices actuales van de 0 a 3.
from bisect import bisect_left
a = [3, 7, 12, 18]
x = 21
posicion = bisect_left(a, x)
existe = posicion < len(a) and a[posicion] == xAquí existe es False. La comprobación del límite evita acceder a a[4]. No uses -1 como contrato de bisect_left: puede devolver cualquier frontera desde 0 hasta len(a), ambos incluidos.
Ejercicio 7. Contar un intervalo de valores
En a = [1, 3, 3, 5, 7, 7, 9, 12], se cuentan los valores v que cumplen 3 <= v < 9 mediante bisect_left(a, 9) - bisect_left(a, 3). ¿Qué cantidad resulta?
A. 3.
B. 4.
C. 6.
D. 5.
Ver solución del ejercicio 7
Correcta: D. Resultan 5 valores: 3, 3, 5, 7 y 7. Las fronteras son 1 y 6, así que el recuento es 6 - 1 = 5.
from bisect import bisect_left
a = [1, 3, 3, 5, 7, 7, 9, 12]
cantidad_intervalo = bisect_left(a, 9) - bisect_left(a, 3)Se incluyen los valores iguales a 3 y se excluye el 9. Cambiar la frontera superior a bisect_right(a, 9) incluiría también los nueves y resolvería otra pregunta. El recuento incluye duplicados: no se pide el número de valores distintos.
Ejercicio 8. Incumplir la precondición de orden
Ejecuta buscar tal como está escrita sobre a = [2, 8, 3, 6, 11], con x = 8. La lista está desordenada y no se ordena antes de llamar. ¿Qué ocurre en esta ejecución?
A. Devuelve 1 porque el valor está en ese índice.
B. Devuelve -1 aunque el valor está en el índice 1.
C. Ordena automáticamente la lista y devuelve 3.
D. Lanza siempre una excepción por detectar el desorden.
Ver solución del ejercicio 8
Correcta: B. Devuelve -1 aunque 8 aparece en el índice 1. Visita los índices 2, 3 y 4, cuyos valores son 3, 6 y 11. Tras ver el 3 del primer sondeo descarta la parte izquierda, precisamente donde estaba 8.
La función no comprueba la ordenación ni la realiza automáticamente; tampoco tiene una instrucción que lance una excepción por este motivo. Este es un contraejemplo concreto a utilizar el algoritmo sin su precondición, no una búsqueda correcta de ausencia. No se usa bisect como comprobación de corrección sobre esta lista desordenada. Ordenar antes cambiaría los índices y tendría un coste propio.
Clave y revisión de errores
La clave es ADBCCADB. Si fallas una traza, anota los límites antes de cada sondeo y comprueba que el intervalo se reduzca. Si fallas con duplicados, identifica primero si se busca cualquier coincidencia, la frontera izquierda o la derecha. Si confundes una frontera con existencia, revisa el caso 6.
En el modelo habitual de acceso por índice, buscar una frontera en una lista ya ordenada tiene coste logarítmico. Eso no convierte una inserción en una lista Python en una operación logarítmica: la documentación de bisect distingue la búsqueda de la inserción, que puede desplazar elementos. No se han cronometrado estos ejemplos ni se atribuyen tiempos a un equipo.
Para practicar trazas de otro tipo de algoritmo, puedes continuar con los ocho ejercicios de FIFO y LRU. Allí se actualiza un estado de páginas residentes; aquí se reduce un intervalo de búsqueda.
El material de Técnico Auxiliar de Informática de Lanzarote incluye el apartado «Algoritmos», que introduce la búsqueda binaria y su precondición de ordenación. Es de pago; consulta su ficha para valorar el alcance. Esta colección amplía la práctica con trazas concretas y no reproduce un examen ni verifica las bases de una convocatoria.
Preguntas frecuentes
¿Qué necesita la búsqueda binaria de estos ejercicios?
Una lista de enteros ordenada de menor a mayor, sin cambios durante la llamada. El caso 8 incumple el orden expresamente para mostrar una búsqueda fallida pese a existir el valor.
¿Los índices empiezan en cero?
Sí. El primer elemento es a[0]. Una lista de n elementos tiene índices de 0 a n - 1, aunque sus puntos de inserción pueden ir de 0 a n.
¿La búsqueda clásica devuelve siempre la primera aparición?
No. La función buscar retorna al encontrar una igualdad. En el caso 3 devuelve el índice 3 aunque la primera aparición está en el 2.
¿bisect_left demuestra que el valor existe?
No. Devuelve una frontera de inserción. Para comprobar existencia en estos ejemplos hay que verificar que la posición sea menor que len(a) y que el elemento de esa posición sea igual al buscado.
¿Un sondeo equivale a una sola comparación del programa?
No necesariamente. Aquí es una iteración que consulta el elemento del índice medio. El código puede evaluar más de una condición en una misma iteración.
