Fala rapaziada do Kode Bro na aula de hoje, nós iremos falar sobre um algoritmo muito importante e utilizado na programação competitiva, que é a Busca Binária na Resposta.

​

Primeiramente antes da explicação do algoritmo, eu recomendo que, se vocês não conheçam o problema Pão a Metro da OBI, lenham ele no link a seguir: https://neps.academy/problem/605, já que ele será utilizado na explicação da Busca Binária na Resposta.

​

Basicamente o objetivo do problema é achar o maior número que a soma da divisão dele pelos tamanhos dos sanduíches seja igual a N e nós conseguimos achar esse número através da implementação do algoritmo da nossa aula.

 

Igualmente na Busca Binária, sempre iremos precisar definir o início e o fim do intervalo em que está a nossa resposta, no problema acima, a nossa resposta pode estar entre 1, já que esse é o valor mínimo de N, e entre o tamanho do maior sanduíche, já que N não pode ser 0. Definido o início e o fim do intervalo da resposta, nós implementamos um while, até que o início seja menor ou igual ao fim(o fato do início ser menor ou igual ao fim varia em relação ao problema, pode ser que o while precise ser implementado com início somente menor que o fim, ou até mesmo em que a diferença entre fim e início seja maior que 1) e assim definimos também o meio do intervalo, igualmente na Busca Binária.

​

Agora é só definir o que irá acontecer durante a nossa Busca Binária. Primeiramente devemos criar uma função que calcule a soma das divisões do "meio" pelos tamanhos dos sanduíches, já que com o resultado dessa função que iremos definir as condições da nossa busca.

 

Se a função retorna um número igual a N, então "meio" é uma resposta possível, porém como queremos a MAIOR resposta possível devemos procurar valores maiores que o "meio", então ini=meio+1.

 

Se a função retorna um valor maior que N, precisamos que a "soma" diminua e assim devemos procurar números maiores que o "meio", já que dessa forma é muito provável que a divisão dos sanduíches por "meio" irá diminuir (por exemplo, se dividimos 8 por 2, recebemos 4, porém se dividimos 8 por um número maior que 2, como 6 recebemos 1).

 

Porém, se a função "corta" retornar um número menor que N, significa que fim=meio-1, pois devemos procurar números menores que "meio", já que assim a "soma" irá aumentar. E por fim, imprimimos a variável fim como resposta, já que ela será a última a ser calculada na nossa Busca Binária.

​

Segue o código para melhor entendimento:

​