Onde posso obter um algoritmo de pesquisa binária C ++ “útil”?

106

Preciso de um algoritmo de pesquisa binária que seja compatível com os contêineres C ++ STL, algo como std::binary_searchno <algorithm>cabeçalho da biblioteca padrão , mas preciso retornar o iterador que aponta para o resultado, não um booleano simples informando se o elemento existe.

(Por outro lado, o que diabos o comitê padrão estava pensando quando definiu a API para binary_search ?!)

Minha principal preocupação aqui é que preciso da velocidade de uma pesquisa binária, embora possa encontrar os dados com outros algoritmos, como mencionado abaixo, quero aproveitar o fato de que meus dados são classificados para obter os benefícios de um binário pesquisa, não uma pesquisa linear.

até agora lower_bounde upper_boundfalhar se o dado estiver faltando:

//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

Observação: também estou bem usando um algoritmo que não pertence ao namespace std, desde que seja compatível com contêineres. Tipo, digamos boost::binary_search,.

Robert Gould
fonte
2
Em relação à edição: é por isso que std :: equal_range é a solução. Caso contrário, você terá que testar a igualdade (ou equivalência para ser mais)
Luc Hermitte
Você deve testar a igualdade após usar (inferior / superior) _bound (consulte a resposta abaixo).
Luc Touraille
A documentação de limite inferior e limite superior afirma que o intervalo deve ser classificado e, por isso, eles podem ser implementados como pesquisa binária.
vividos
@vividos, viva! você encontrou apenas a documentação que eu precisava saber! Obrigado!
Robert Gould
Robert, os algoritmos limite inferior / limite superior / intervalo igual não funcionam com intervalos não classificados. Você tem sorte de vê-los trabalhando com a amostra de elementos que você tirou.
Luc Hermitte

Respostas:

97

Não existem tais funções, mas você pode escrever uma simples usando std::lower_bound, std::upper_boundou std::equal_range.

Uma implementação simples pode ser

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}

Outra solução seria usar a std::set, que garante a ordem dos elementos e fornece um método iterator find(T key)que retorna um iterador para o item fornecido. No entanto, seus requisitos podem não ser compatíveis com o uso de um conjunto (por exemplo, se você precisar armazenar o mesmo elemento várias vezes).

Luc Touraille
fonte
sim isso funciona, e eu tenho uma implementação semelhante agora, porém é uma implementação "ingênua", no sentido de que não está fazendo uso do contexto da situação, neste caso dados classificados.
Robert Gould
5
Eu realmente não entendo seu comentário, já que lower_bound só pode ser usado em dados classificados. A complexidade é menor do que usar find (veja editar).
Luc Touraille
4
Para complementar a resposta de Luc, verifique o artigo clássico de Matt Austern Por que você não deve usar set e o que você deve usar (Relatório C ++ 12: 4, abril de 2000) para entender por que a pesquisa binária com vetores classificados é geralmente preferível a std :: set , que é um contêiner associativo baseado em árvore.
ZunTzu
16
Não use *i == val! Em vez disso, use !(val < *i). A razão é que lower_boundusa <, não ==(ou Tseja, não é nem mesmo exigido que seja comparável em igualdade). (Veja o STL efetivo de Scott Meyers para uma explicação da diferença entre igualdade e equivalência .)
gx_
1
@ CanKavaklıoğlu Não há nenhum elemento localizado em end. Os intervalos na biblioteca padrão C ++ são representados com intervalos semiabertos: o iterador final "aponta" após o último elemento. Como tal, pode ser retornado por algoritmos para indicar que nenhum valor foi encontrado.
Luc Touraille
9

Você deveria dar uma olhada std::equal_range. Ele retornará um par de iteradores para o intervalo de todos os resultados.

Luc Hermitte
fonte
De acordo com cplusplus.com/reference/algorithm/equal_range, o custo de std :: equal_range é aproximadamente o dobro de std :: lower_bound. Parece que envolve uma chamada para std :: lower_bound e uma chamada para std :: upper_bound. Se você sabe que seus dados não têm duplicatas, isso é um exagero e std :: lower_bound (como demonstrado na primeira resposta) é a melhor escolha.
Bruce Dawson
@BruceDawson: cplusplus.com fornece apenas uma implementação de referência para especificar o comportamento ; para uma implementação real, você pode verificar sua biblioteca padrão favorita. Por exemplo, em llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm , podemos ver que as chamadas para lower_bound e upper_bound são feitas em intervalos disjuntos (após alguma pesquisa binária manual). Dito isso, é provável que seja mais caro, especialmente em intervalos com vários valores correspondentes.
Matthieu M.
6

Existe um conjunto deles:

http://www.sgi.com/tech/stl/table_of_contents.html

Procurar por:

Em uma nota separada:

Eles provavelmente estavam pensando que pesquisar contêineres poderia levar a mais de um resultado. Mas na ocasião ímpar em que você só precisa testar a existência, uma versão otimizada também seria bom.

Martin York
fonte
3
binary_search não retorna um iterador como mencionei anteriormente, é por isso que estou procurando uma alternativa.
Robert Gould
1
Sim eu conheço. Mas ele se encaixa no conjunto de algoritmos de busca binária. Portanto, é bom que os outros conheçam.
Martin York
8
binary_search é apenas, como tantas outras coisas no STL, nomeado errado. Eu odeio isso. Testar a existência não é o mesmo que procurar algo.
OregonGhost de
2
Essas funções de pesquisa binária não são úteis no caso de você querer saber o índice do elemento que está procurando. Tenho que escrever minha própria função recursiva para esta tarefa. Espero que este, template <class T> int bindary_search (const T & item), seja adicionado à próxima versão do C ++.
Kemin Zhou
3

Se std :: lower_bound for de nível muito baixo para o seu gosto, você pode querer verificar boost :: container :: flat_multiset . É uma substituição drop-in para std :: multiset implementado como um vetor ordenado usando busca binária.

ZunTzu
fonte
1
Bom link; e também um bom link no link: lafstern.org/matt/col1.pdf , que descreve como as pesquisas implementadas com um vetor classificado, em vez de definidas (embora ambos sejam log (N)), têm constantes de proporcionalidade significativamente melhores e são ~ duas vezes mais rápido (a desvantagem é um tempo de INSERÇÃO maior).
Dan Nissenbaum de
2

A implementação mais curta, perguntando por que não está incluída na biblioteca padrão:

template<class ForwardIt, class T, class Compare=std::less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
    // Note: BOTH type T and the type after ForwardIt is dereferenced 
    // must be implicitly convertible to BOTH Type1 and Type2, used in Compare. 
    // This is stricter than lower_bound requirement (see above)

    first = std::lower_bound(first, last, value, comp);
    return first != last && !comp(value, *first) ? first : last;
}

De https://en.cppreference.com/w/cpp/algorithm/lower_bound

Trozen
fonte
Posso pensar em dois motivos pelos quais isso não está na biblioteca padrão: Eles acham que é fácil de implementar, mas o principal motivo é provavelmente que pode exigir uma versão invertida de operator () () se o valor não for intercambiável com * primeiro.
user877329
1

Verifique esta função, qBinaryFind :

RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )

Executa uma pesquisa binária do intervalo [início, fim) e retorna a posição de uma ocorrência de valor. Se não houver ocorrências de valor, retorna fim.

Os itens no intervalo [início, fim) devem ser classificados em ordem crescente; veja qSort ().

Se houver muitas ocorrências do mesmo valor, qualquer uma delas pode ser retornada. Use qLowerBound () ou qUpperBound () se precisar de um controle mais preciso.

Exemplo:

QVector<int> vect;
 vect << 3 << 3 << 6 << 6 << 6 << 8;

 QVector<int>::iterator i =
         qBinaryFind(vect.begin(), vect.end(), 6);
 // i == vect.begin() + 2 (or 3 or 4)

A função está incluída no <QtAlgorithms> cabeçalho que faz parte da biblioteca Qt .

Lawand
fonte
1
Infelizmente, esse algoritmo não é compatível com contêineres STL.
Bartolo-otrit
0

std :: lower_bound () :)

moogs
fonte
OP: "até agora o limite inferior e limite superior falham, porque ..."
sublinhado_d
0
int BinarySearch(vector<int> array,int var)
{ 
    //array should be sorted in ascending order in this case  
    int start=0;
    int end=array.size()-1;
    while(start<=end){
        int mid=(start+end)/2;
        if(array[mid]==var){
            return mid;
        }
        else if(var<array[mid]){
            end=mid-1;
        }
        else{
            start=mid+1;
        }
    }
    return 0;
}

Exemplo: Considere uma matriz, A = [1,2,3,4,5,6,7,8,9] Suponha que você queira pesquisar o índice de 3 Inicialmente, início = 0 e fim = 9-1 = 8 Agora , desde início <= fim; mid = 4; (array [mid] que é 5)! = 3 Agora, 3 está à esquerda do meio, pois é menor que 5. Portanto, pesquisamos apenas a parte esquerda do array. Portanto, agora start = 0 e end = 3; mid = 2. Desde array [mid] == 3, portanto, obtivemos o número que estávamos procurando. Portanto, retornamos seu índice que é igual a mid.

Siddharth Kumar Shukla
fonte
1
É bom ter código, mas você pode melhorar a resposta fornecendo uma breve explicação de como ele funciona para pessoas que são novas na linguagem.
Taegost de
Alguém sinalizou incorretamente sua postagem como de baixa qualidade . Uma resposta apenas em código não é de baixa qualidade . Tenta responder à pergunta? Caso contrário, sinalize como 'não é uma resposta' ou recomende a exclusão (se estiver na fila de revisão). b) É tecnicamente incorreto? Votar negativamente ou comentar.
Wai Ha Lee
0

Uma solução que retorna a posição dentro do intervalo pode ser assim, usando apenas operações em iteradores (deve funcionar mesmo se o iterador não fizer cálculos):

template <class InputIterator, typename T>
size_t BinarySearchPos(InputIterator first, InputIterator last, const T& val)
{       
    const InputIterator beginIt = first;
    InputIterator element = first;
    size_t p = 0;
    size_t shift = 0;
    while((first <= last)) 
    {
        p = std::distance(beginIt, first);
        size_t u = std::distance(beginIt, last);
        size_t m = p + (u-p)/2;  // overflow safe (p+u)/2
        std::advance(element, m - shift);
        shift = m;
        if(*element == val) 
            return m; // value found at position  m
        if(val > *element)
            first = element++;
        else
            last  = element--;

    }
    // if you are here the value is not present in the list, 
    // however if there are the value should be at position u
    // (here p==u)
    return p;

}
Michele Belotti
fonte