Búsqueda Binaria
Imagina que hemos anotado las alturas de todos los edificios del mundo en orden ascendente. Así, el primer elemento corresponde al edificio más bajo del mundo y el último al más alto. Jugamos a un juego en el que, dada una altura de edificio como consulta (query), debemos responder con la posición (índice) de ese edificio en la lista. Si no existe ningún edificio con la altura solicitada, respondemos con -1.
Un enfoque ingenuo sería usar un bucle
for que recorra cada elemento del arreglo y compruebe si coincide con la consulta. En el peor de los casos, se realizarían n operaciones para cada consulta (si el número de elementos en el arreglo es n).h = [...] # Alturas de todos los edificios en orden ascendente
q = int(input()) # La altura consultada
for i, height in enumerate(h):
if height == q: # En caso de encontrar el elemento
print(i) # Imprimir el índice
break # Y detenerse
else: # Si no encontramos un edificio con altura q (else = nobreak)
print(-1) # Imprimir -1 para indicar que no lo hallamosSin embargo, al notar que la lista está en orden ascendente, vemos que realizamos muchas operaciones innecesarias. En lugar de recorrer la lista desde el principio hasta el final, podríamos saltar ciertos pasos redundantes y llegar a la respuesta más rápido.
Como el arreglo está ordenado, una estrategia más óptima consiste en examinar el elemento de en medio. Si este es menor que
q, desechamos la mitad izquierda del arreglo y nos concentramos solo en la parte derecha. Si es mayor que q, desechamos la mitad derecha y nos quedamos con la parte izquierda. Este proceso de verificar el elemento central y descartar la mitad sobrante hasta encontrar el valor buscado es, esencialmente, el algoritmo de Búsqueda Binaria.h = [...] # Alturas de todos los edificios en orden ascendente
q = int(input()) # La altura consultada
l, r = 0, len(h) # La respuesta siempre está entre [l; r). Observa que r es exclusivo
while r - l > 1: # Hay al menos un elemento que considerar en medio
mid = (l + r) // 2 # Tomar el índice del medio
if h[mid] > q: # h[mid] > q => descartar la mitad derecha
r = mid
else: # h[mid] <= q => descartar la mitad izquierda
l = mid
# Al final, h[l] debería ser el elemento consultado
print(l if h[l] == q else -1)Imagina que tenemos un arreglo de alturas de edificios
h = [20, 22, 23, 23, 34, 49, 52, 55, 58] y queremos saber el índice del edificio con altura 49.Con dicho algoritmo, haríamos varias iteraciones:
mid = (0 + 9) // 2 = 4⇒h[4] = 34≤49⇒ descartamos la parte izquierda.
mid = (4 + 9) // 2 = 6⇒h[6] = 52>49⇒ descartamos la parte derecha.
mid = (4 + 6) // 2 = 5⇒h[5] = 49≤49⇒ descartamos la parte izquierda.
l = 5,r = 6⇒r - l == 1⇒ el bucle while termina y se imprime 5 porqueh[5] = 49.
Este pequeño ejemplo quizá no parezca una gran optimización, pero imagina que tuviéramos 10 mil millones de edificios. En el caso de recorrer cada elemento uno por uno, realizaríamos 10 mil millones de iteraciones en el peor de los casos. En cambio, al dividir el arreglo a la mitad en cada iteración y desechar la parte sobrante, el ahorro de tiempo es enorme. Veamos cuántas iteraciones tardaríamos en llegar a la respuesta si partiéramos los 10 mil millones de elementos cada vez:
Spoiler: son solo 32 iteraciones en lugar de 10 mil millones
- 10,000,000,000 / 2 = 5,000,000,000
- 5,000,000,000 / 2 = 2,500,000,000
- 1250000000 / 2 = 625000000
- 625000000 / 2 = 312500000
- 312500000 / 2 = 156250000
- 156250000 / 2 = 78125000
- 78125000 / 2 = 39062500
- 39062500 / 2 = 19531250
- 19531250 / 2 = 9765625
- 9765625 / 2 = 4882812
- 4882812 / 2 = 2441406
- 2441406 / 2 = 1220703
- 1220703 / 2 = 610351
- 610351 / 2 = 305175
- 305175 / 2 = 152587
- 152587 / 2 = 76293
- 76293 / 2 = 38146
- 38146 / 2 = 19073
- 19073 / 2 = 9536
- 9536 / 2 = 4768
- 4768 / 2 = 2384
- 2384 / 2 = 1192
- 1192 / 2 = 596
- 596 / 2 = 298
- 298 / 2 = 149
- 149 / 2 = 74
- 74 / 2 = 37
- 37 / 2 = 18
- 18 / 2 = 9
- 9 / 2 = 4
- 4 / 2 = 2
- 2 / 2 = 1
Así, imagina un algoritmo que haga una búsqueda lineal revisando cada elemento en una colección de 10 mil millones de objetos, y que cada comprobación tarde 1 segundo. Ese algoritmo tardaría 317 años en completarse. En cambio, la búsqueda binaria tardaría solo 32 segundos.
Esta es la diferencia entre realizar operaciones de orden y operaciones de orden .
Desafío
Dados
n GPAs del 1 al 4 (1 es la nota más baja y 4 la más alta), y varios umbrales, se pide determinar cuántas personas pasarían al siguiente grado si necesitan tener el umbral o un valor mayor para aprobar.Entrada
La primera línea de la entrada contiene un solo entero
n (1 ≤ n ≤ ), que es el número de estudiantes.La siguiente línea contiene
n números de punto flotante que representan los GPAs de los estudiantes en orden ascendente (1 ≤ ≤ 4).La tercera línea contiene un solo entero
q (1 ≤ q ≤ ), que es el número de umbrales a considerar.La última línea de la entrada contiene
q números de punto flotante que representan los mínimos umbrales necesarios para pasar de grado (1 ≤ ≤ 4).Salida
El programa debe imprimir
q líneas. La línea i debe mostrar cuántos estudiantes pasarían al siguiente grado dado el umbral .Ejemplos
Entrada | Salida |
10
1.1 1.2 1.4 1.7 2 3 3.3 3.5 3.8 3.8
5
3.7
3.8
1
1.5
2 | 2
2
10
7
6 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB