Binary Search

Código padrão para Busca Binária em inteiros

auto check = [&](int k) {
   ... // check se é possível realizar a operação com K
};

int lo = 0, hi = n - 1, mi; // trocar o LO e HI por valores limite
while(lo < hi) {
   mi = (lo + hi) / 2;
   if (check(mi)) hi = mi;
   else lo = mi + 1;
}
return lo;

auto check = [&](int k) {
   ... // check se é possível realizar a operação com K
};

int lo = 0, hi = n - 1, mi; // trocar o LO e HI por valores limite
while(lo < hi) {
   mi = (lo + hi + 1) / 2;
   if (check(mi)) lo = mi;
   else hi = mi - 1;
}
return lo;

Código para double

auto check = [&](double k) {
   ... // check se é possível realizar a operação com K
};

const double EPS = 1e-9; // limiar de erro aceitável

double lo = 0, hi = 1e9, mi; // trocar o LO e HI por valores limite
while(hi - lo > EPS) {
   mi = (lo + hi) / 2;
   if (check(mi)) lo = mi;
   else hi = mi;
}
return lo;

Porém, também é possível fazer de outro jeito, "limitando" a quantidade de operações

auto check = [&](double k) {
   ... // check se é possível realizar a operação com K
};

int CNT = 200; // fazer 200 operações

double lo = 0, hi = 1e9, mi; // trocar o LO e HI por valores limite
while(CNT--) {
   mi = (lo + hi) / 2;
   if (check(mi)) lo = mi;
   else hi = mi;
}
return lo;

Ideia principal para saber se é lo+1, hi-1, (lo+hi)/2 ou (lo+hi+1)/2, etc

• Imaginar um eixo com todos os valores possíveis

  

• Pensar no valor possível mi e se ele vai limitar o "lo" ou o "hi"

  

• Se for alterar o "hi = mi", ou seja, o mi entra na resposta e limita superiormente:

  while(lo < hi) {
     mi = (lo + hi) / 2;
     if (check(mi)) hi = mi;
     else lo = mi + 1;
  }
  

• Se for alterar o "lo = mi", ou seja, o mi entra na resposta e limita inferiormente:

  while(lo < hi) {
     mi = (lo + hi + 1) / 2; // tem que colocar o +1 para evitar loop infinito
     if (check(mi)) lo = mi;
     else hi = mi - 1;
  }
  

• Essa diferença em (lo+hi)/2 ou (lo+hi+1)/2 vem de quando o intervalo entre (lo, hi) é de tamanho 1, ou seja, hi = lo + 1

  • Se deixar mi=(lo+hi)/2, ele vai falar que mi=lo, então se você fizer depois lo=mi, não vai mudar nada. Por isso que precisa fazer mi=(lo+hi+1)/2

Exercícios auxiliares

A - Computer Game

B - WiFi