Pesquisa Binária
Imagine que escrevemos as alturas de todos os edifícios do mundo em ordem crescente. Assim, o primeiro elemento da lista é o edifício mais baixo do mundo e o último é o mais alto. Jogamos um jogo em que, dado um valor inteiro que representa a altura de um edifício, devemos responder com a posição (o índice) desse edifício na lista. Caso não exista nenhum edifício com a altura solicitada, respondemos com -1.
Uma abordagem mais simples seria percorrer cada elemento do array com um loop
for e verificar se coincide com a altura pesquisada. No pior dos casos, isso causaria n operações para cada consulta (se a lista possui n elementos).h = [...] # Alturas de todos os edifícios em ordem crescente
q = int(input()) # A altura consultada
for i, height in enumerate(h):
if height == q: # Caso encontremos o elemento
print(i) # Imprime o índice
break # E interrompe
else: # Caso não encontremos um edifício com altura q (else = sem break)
print(-1) # Imprime -1 para indicar a ausênciaNo entanto, percebendo que a lista está ordenada em ordem crescente, começamos a notar que estamos a fazer muitas operações redundantes. Em vez de percorrer toda a lista do início ao fim, poderíamos descartar partes inúteis e chegar à resposta mais rapidamente.
Como o array inteiro está ordenado, uma forma mais eficiente de resolver este problema é olhar para o elemento do meio do array. Se esse elemento for menor do que
q, descartamos toda a metade esquerda e concentramos a pesquisa apenas na direita. Se esse elemento for maior do que q, descartamos a metade direita e pesquisamos apenas na esquerda. Repetir este procedimento, procurando sempre o elemento do meio e descartando a metade redundante até encontrar o elemento, é essencialmente o algoritmo de Pesquisa Binária.h = [...] # Alturas de todos os edifícios em ordem crescente
q = int(input()) # A altura consultada
l, r = 0, len(h) # A resposta estará sempre entre [l; r). Note que r é exclusivo
while r - l > 1: # Existe pelo menos um elemento para considerar
mid = (l + r) // 2 # Pegar o índice do meio
if h[mid] > q: # h[mid] > q => descartar a metade direita
r = mid
else: # h[mid] <= q => descartar a metade esquerda
l = mid
# No fim, vamos verificar se h[l] é, de fato, o elemento consultado
print(l if h[l] == q else -1)Imagine que temos um array de alturas de edifícios
h = [20, 22, 23, 23, 34, 49, 52, 55, 58] e queremos saber o índice do edifício com altura 49.Com este algoritmo, faremos várias iterações:
mid = (0 + 9) // 2 = 4⇒h[4] = 34≤49⇒ descartamos a parte esquerda.
mid = (4 + 9) // 2 = 6⇒h[6] = 52>49⇒ descartamos a parte direita.
mid = (4 + 6) // 2 = 5⇒h[5] = 49≤49⇒ descartamos a parte esquerda.
l = 5,r = 6⇒r - l == 1⇒ o ciclo termina e imprimimos 5, poish[5] = 49.
Este pequeno exemplo pode não parecer grande coisa em termos de otimização, mas imagine que temos 10 mil milhões de edifícios. Se fôssemos percorrer todos os elementos, no pior caso faríamos 10 mil milhões de iterações. Já ao partir o array ao meio repetidamente e descartar as partes redundantes, o ganho de desempenho é enorme. Vejamos quantas iterações seriam necessárias para chegar a uma resposta, dividindo 10 mil milhões de elementos ao meio em cada iteração:
Spoiler: seriam apenas 32 iterações em vez de 10 mil milhões
- 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
Agora imagine que exista um algoritmo que faça uma pesquisa linear, verificando cada um dos 10 mil milhões de itens e que analisar cada elemento demore 1 segundo. Esse algoritmo demoraria 317 anos para terminar. Enquanto isso, um algoritmo de pesquisa binária levaria apenas 32 segundos!
Esta é a diferença entre fazer operações e operações.
Desafio
Dadas
n médias (GPAs) entre 1 e 4 (sendo 1 a nota mais baixa e 4 a nota perfeita) e vários valores limite, a tarefa é determinar quantas pessoas passariam para o próximo nível, considerando que, para passar, o valor da média deve ser igual ou superior a esse limite.Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ), que é o número de estudantes.A linha seguinte contém
n números em ponto flutuante que representam as médias dos estudantes em ordem crescente (1 ≤ ≤ 4).A terceira linha contém um único inteiro
q (1 ≤ q ≤ ), que é o número de valores limite a considerar.A última linha da entrada contém
q números em ponto flutuante que representam os limites mínimos para passar de nível (1 ≤ ≤ 4).Saída
O programa deve imprimir
q linhas. A linha i deve representar o número de estudantes que passariam de nível dado o limite .Exemplos
Entrada | Saída |
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