Algoritmo de busca em vetores baseado em divisão e conquista
Autor(es):
vet = {2, 5, 7, 8, 10}
buscar(vet, 7) = 2 //o elemento 7 está na posição 2 do vetor
buscar(vet, 2) = 0 //o elemento 2 está na posição 0 do vetor
buscar(vet, 3) = -1 //o elemento 3 não se encontra no vetor
int buscaLinear(vector<int> vet, int x)
{
for(int i = 0; i < vet.size(); i++)
{
if (vet[i] == x)
return i;
}
return -1;
}
vetor, teremos que percorrer todas as n posições do vetor.
vet = {0, 4, 6, 9, 10, … }
/*Se buscarmos o número 7 nesse vetor (sabendo que ele está ordenado),
assim que passarmos pela posição 3 vamos saber que ele não se encontra no
vetor, mesmo que ele tenha mais 100000 elementos*/
int buscaLinearOrd(vector<int> vet, int x)
{
for(int i = 0; i < vet.size(); i++)
{
if (vet[i] == x)
return i;
if (vet[i] > x)
break;
}
return -1;
}
centro = (inicio + fim) / 2
Se vet[centro] == x, então o elemento está na posição “centro”
Se vet[centro] > x, então x só pode estar entre vet[inicio] e vet[centro - 1]
Se vet[centro] < x, então x só pode estar entre vet[centro + 1] e vet[fim]
int buscaBinaria(int vet[], int esq, int dir, int x)
{
if (esq > dir)
return -1;
int meio = (esq + dir)/2;
if (vet[meio] > x)
return buscaBinaria(vet, esq, meio-1, x);
if (vet[meio] < x)
return buscaBinaria(vet, meio+1, dir, x);
return meio;
}
int buscaBinaria2(int vet[], int n, int x)
{
int esq = 0, dir = n - 1, meio;
while(esq <= dir) {
meio = (esq + dir)/2;
if (vet[meio] == x) return meio;
if (vet[meio] > x) dir = meio - 1;
else esq = meio + 1;
}
return -1;
}
Problema M: Maratona Brasileira de Comedores de pipocas
A competição consiste em N sacos de pipocas colocados lado a lado, onde cada saco possui uma quantidade arbitrária de pipoca.
A competição ocorrem em equipes, cada uma composta por C competidores, e cada competidor pode comer, no máximo, até T pipocas por segundos.
Cada competidor da equipe deverá comer uma sequência contígua de sacos de pipocas. É perfeitamente válido que um competidor não coma nenhuma pipoca.
Todas as pipocas de um mesmo saco devem ser comidas por um único competidor.
O objetivo da competição é comer todas as pipocas no menor tempo possível, dado que os C competidores podem comer em paralelo e eles respeitarão todas as regras impostas.
Entrada
N = quantidade de sacos de pipocas (<= 105)
C = quantidade de competidores de uma mesma equipe
T = quantidade máxima de pipoca/s que um competidor pode comer
Pi = quantidade de pipocas no saco i
bool ehPossivel(vector<int> &pip, int c, int x){
int soma = 0, competidorAtual = 0;
for(int i = 0; i < pip.size(); i++){
soma += pip[i];
if (soma > x){
competidorAtual++;
if (competidorAtual == c)
return false;
soma = pip[i];
}
}
return true;
}
int solve(vector<int> &pip, int c, int t_ini, int t_fim){
int x, k = t_fim;
while(t_ini <= t_fim){
x = (t_ini + t_fim)/2;
if (ehPossivel(pip, c, x)){
k = x;
t_fim = x - 1;
} else {
t_ini = x + 1;
}
}
return k;
}
Como identificar se um problema pode ser resolvido por busca binária?
É difícil determinar uma regra geral, além de que depende muito da modelagem e da forma que você está representando o problema.
Mas uma dica importante é determinar se o problema possui um caráter monotônico como o exercício anterior.
Pode ser descrito por uma função crescente ou decrescente.
Exemplo de problema recorrente: determinar o menor x tal que f(x) >= k.
img10.png
double raiz(double x, double eps=1e-3){
double l = 0, r = x;
double m;
while (r-l > eps){
m = (l+r)/2;
//cout << m << endl;
if (m*m < x)
l = m;
else
r = m;
}
return (l+r)/2;
}
sqrt(2) = 1.41421
1 1.5 1.25 1.375 1.4375 1.40625 1.42188 1.41406 1.41797
1.41602 1.41504 1.41455
raiz(2) = 1.41455
Referências
http://www.ic.unicamp.br/~zanoni/mc102/2013-1s/aulas/aula15.pdf
http://www.dcc.fc.up.pt/~pribeiro/aulas/daa1617/slides/2_ordenacao_07102016.pdf
https://www.ic.unicamp.br/~ripolito/peds/mc102z/material/aula13.pdf
https://www.youtube.com/watch?v=GU7DpgHINWQ
https://codeforces.com/blog/entry/76686
https://sites.google.com/site/calcnum10/home/lista-2/metodos/metodo-da-bisseccao
https://noic.com.br/materiais-informatica/curso/techniques-01/