CKTIS / C++
Ordenação, comparações e intervalos de pesquisa
Uma ordenação correta requer um comparador que defina uma ordem fraca estrita. A pesquisa binária requer um intervalo particionado de acordo com a condição relevante; ordenar todo o intervalo é suficiente, mas nem sempre necessário.
Versão: C++23; repository compiler flag, production runtime not attested
Sintaxe
std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);std::sort de <algorithm> ordena o intervalo semiaberto [first, last) segundo comp: nenhum elemento posterior precede um elemento anterior. Requer iteradores de acesso aleatório e elementos que cumpram os requisitos de movimentação e troca. Efetua O(N log N) comparações. Não garante a preservação da ordem dos elementos equivalentes; para isso, use std::stable_sort.
O comparador tem de definir uma ordem fraca estrita. comp(a, b) significa que a precede b, e comp(a, a) tem de ser falso. A relação tem de ser transitiva. A equivalência definida por !comp(a, b) && !comp(b, a) também tem de ser transitiva e não tem necessariamente de coincidir com operator==. Não use <=: viola o requisito para argumentos idênticos. Se os requisitos do comparador não forem cumpridos, as garantias do algoritmo deixam de se aplicar.
A ordem fraca estrita e a partição dos intervalos de pesquisa são requisitos relacionados, mas distintos. Num intervalo particionado segundo um predicado, todos os elementos cujo resultado é true surgem antes dos que dão false; qualquer uma das partes pode estar vazia. Para std::lower_bound(first, last, value, comp), o predicado é comp(e, value). A função devolve a fronteira: o primeiro elemento cujo resultado é false, ou last. Isto não confirma que o valor pesquisado está presente; não desreferencie last.
Ordenar segundo a mesma ordem garante esta partição para qualquer chave. Para uma única chave, basta a partição: [2, 1, 4, 3] cumpre a pré-condição de std::lower_bound para value = 3 e a comparação <, apesar de não estar ordenado. As outras funções de pesquisa binária têm requisitos de partição próprios. std::lower_bound efetua O(log N) comparações, mas, sem iteradores de acesso aleatório, pode exigir um número linear de passos do iterador.
O exemplo ordena números inteiros e, em seguida, usa o mesmo comp para obter o índice 3. O conteúdo tem como objetivo C++23; a referência fornecida aponta para um rascunho de trabalho em evolução, não para uma publicação C++23 definitiva. O suporte do compilador e do ambiente de execução de produção não está atestado.
Exemplos
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{4, 1, 3, 1, 2};
const auto comp = [](int a, int b) { return a < b; };
std::sort(values.begin(), values.end(), comp);
for (std::size_t i = 0; i < values.size(); ++i) {
if (i != 0) std::cout << ' ';
std::cout << values[i];
}
std::cout << '\n';
const auto it = std::lower_bound(values.begin(), values.end(), 3, comp);
std::cout << "index=" << (it - values.begin()) << '\n';
}
Resultado
1 1 2 3 4 index=3
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.