Pesquisa em arrays e pesquisa de resposta

Em [1,3,3,3,8], encontrar um 3 não resolve todas as consultas. A primeira posição é 1 e há três ocorrências. Fixa o resultado antes de escolheres a pesquisa: qualquer ocorrência, a primeira, a contagem ou a primeira posição que satisfaz uma condição.

lower_bound(x) devolve uma posição de inserção: a primeira posição com valor maior ou igual a x. Não devolve «o valor encontrado». A contagem obtém-se por diferença entre os dois limites, sem desreferenciar fronteiras.

Pesquisa sequencial

Percorre todas as posições até encontrares o valor. Funciona num vetor desordenado, usa espaço auxiliar $O(1)$ e tem pior caso $\Theta(n)$. O melhor caso é $\Theta(1)$ se encontrares o primeiro elemento. Com um alvo presente e uniformemente distribuído pelas posições, a média é $(n+1)/2$ comparações. Sem uma hipótese sobre as entradas, não existe essa média garantida.

Uma sentinela pode eliminar a verificação do fim dentro do ciclo, mas exige espaço extra ou alteração temporária da entrada. Tens de distinguir a sentinela de uma ocorrência real e repor qualquer valor alterado. Não altera a ordem linear do custo.

Ordenar uma vez para responderes a q pesquisas custa $O(n\log n+q\log n)$. Pesquisar sequencialmente custa $O(nq)$. Com uma única pesquisa, ordenar primeiro costuma ser trabalho desnecessário. Se precisas das posições originais, guarda-as antes de ordenar.

Pesquisa binária com limites

Num vetor ordenado por ordem crescente, lower_bound(x) é a primeira posição com valor maior ou igual a x. upper_bound(x) é a primeira posição com valor estritamente maior. Ambas podem devolver n, a posição depois do último elemento. Não acedas a v[n].

Confirma que o valor existe antes de o leres: verifica l<n e v[l]==x. Se as fronteiras coincidem, a contagem é zero.

Para o limite inferior, mantém [l,r), começando em [0,n):

• Todas as posições antes de l contêm valores menores que x.
• Todas as posições a partir de r contêm valores maiores ou iguais a x.
• A fronteira procurada está entre l e r, incluindo os extremos.

Calcula m=l+(r-l)/2. Se v[m]<x, a ordenação permite excluir todo [l,m], ficando l=m+1. Caso contrário, m ainda pode ser a primeira posição válida, pelo que fazes r=m. O intervalo perde pelo menos uma posição. Ao terminar, l=r e as duas regiões conhecidas provam a resposta.

No limite superior, a região descartada à esquerda contém valores menores ou iguais a x. O teste passa a v[m]<=x. A diferença entre os dois limites conta as ocorrências, incluindo zero quando o alvo falta.

#include <iostream>
#include <vector>
enum class Limite { inferior, superior };
std::size_t limite(const std::vector<int>& v, int x, Limite tipo) {
    std::size_t l = 0, r = v.size();
    while (l < r) {
        const std::size_t m = l + (r - l) / 2;
        if (v[m] < x || (tipo == Limite::superior && v[m] == x)) l = m + 1;
        else r = m;
    }
    return l;
}
int main() {
    const std::vector<int> v{1, 3, 3, 3, 8};
    for (int x : {0, 3, 9}) {
        const auto l = limite(v, x, Limite::inferior), r = limite(v, x, Limite::superior);
        std::cout << x << ": " << l << ' ' << r << ' ' << r - l << '\n';
    }
    std::cout << "vazio: " << limite({}, 3, Limite::inferior) << '\n';
}

O programa trata também o alvo menor que o mínimo, maior que o máximo e o vetor vazio. Em C++, std::lower_bound e std::upper_bound devolvem iteradores; num vector, a diferença entre iteradores dá a posição. Em iteradores apenas de avanço, o número de comparações continua logarítmico, mas os avanços podem ser lineares. Num set, prefere o método set.lower_bound.

Para q consultas «quantos valores são diferentes de x?», ordena uma vez e devolve n-(upper_bound(x)-lower_bound(x)), usando posições ou diferenças de iteradores do vetor. Se x faltar, as fronteiras coincidem e todos os n valores são diferentes; se for o máximo, o limite superior pode ser n. Não precisas de desreferenciar nenhuma fronteira. Com comparações constantes, o total é $O(n\log n+q\log(n+1))$.

Com strings de no máximo M caracteres, cada comparação pode custar $O(M)$, dando $O(M\log(n+1))$ por pesquisa binária num vetor. Numa lista ligada ordenada, obter o elemento do meio exige avanços pelas ligações; a ordenação não elimina esse custo. Copiar a sequência já ordenada para um vetor uma vez pode compensar muitas consultas, incluindo o custo de copiar as strings.

Num vetor não vazio ordenado, o máximo é v.back(): a primeira ocorrência do máximo é o seu limite inferior. Devolver sempre n-1 daria a última ocorrência quando há empates.

O custo no vetor é $O(\log(n+1))$ e o espaço auxiliar é $O(1)$. Usar [l,r) evita um índice -1 num tipo sem sinal e dispensa um caso especial para n=0. Alterar só um dos limites sem reveres o invariante pode causar um ciclo infinito ou saltar uma ocorrência.

Pesquisa binária da resposta

A pesquisa binária também encontra a menor resposta viável, mesmo sem um vetor explícito. Precisas de um predicado monótono: falso para respostas demasiado pequenas e verdadeiro a partir de uma fronteira.

Divide pesos positivos [4,6,3,7] em no máximo dois grupos contíguos, minimizando a maior soma. Para um limite M, percorre da esquerda para a direita e acrescenta pesos ao grupo atual enquanto couberem; quando o próximo exceder M, abre outro grupo. Se algum peso exceder M, a resposta é inviável.

A estratégia gulosa usa o menor número de grupos: o primeiro grupo termina tão tarde quanto é permitido. Qualquer solução válida não pode terminar o seu primeiro grupo mais à direita. Repetindo o argumento no sufixo, a solução gulosa nunca precisa de mais grupos que outra solução.

Se M funciona, um limite maior também funciona, porque a mesma divisão continua válida. Pesquisa no intervalo fechado entre o maior peso e a soma total, convertendo o esquema para uma primeira resposta verdadeira. Cada avaliação do predicado percorre o vetor em $O(n)$; a pesquisa faz $O(\log(S+1))$ avaliações, logo o total é $O(n\log(S+1))$ com espaço auxiliar constante. Contar apenas as divisões do intervalo omite o percurso do vetor em cada teste. Com [5,2,8,4] e no máximo dois grupos, os limites são 8 e 19; M=11 exige três grupos e M=12 usa [5,2] e [8,4].

Pesos negativos invalidam a justificação gulosa. «Exatamente k grupos não vazios» só equivale a «no máximo k» aqui quando 1<=k<=n, porque podes subdividir grupos de pesos positivos sem aumentar a soma máxima. Declara esta condição antes de reutilizares o predicado.

Bisseção em números reais

Para encontrares uma raiz de uma função contínua com sinais opostos nos extremos, calcula o meio e conserva a metade que mantém a mudança de sinal. A continuidade garante a existência de uma raiz; não garante que seja única. Uma função com uma raiz de multiplicidade par pode não mudar de sinal.

Em $f(x)=x^2-3$, no intervalo [1,2], os primeiros meios são 1,5, 1,75 e 1,625. Os novos intervalos são [1,5;2], [1,5;1,75] e [1,625;1,75]. Após k divisões, a largura é $1/2^k$. Usar o meio final dá erro absoluto de localização no máximo metade da largura, em aritmética exata.

Com double, termina também se o meio for igual a um extremo ou atingires um limite de iterações. Compara os sinais diretamente, em vez de multiplicares dois valores que podem exceder o intervalo representável. Um teste de valor pequeno de f(x) e um teste de intervalo pequeno medem coisas diferentes. Para $\sqrt3$, a aproximação a seis casas decimais é 1,732051.

Pesquisa discreta exige monotonia do predicado; bisseção com mudança de sinal exige continuidade. Justifica a hipótese usada antes de descartares metade do espaço de respostas.