Problema com algoritmo de pesquisa
Estou trabalhando em um projeto eu estou com uma demanda de fazer uma barra de pesquisa em uma tabela, pensei em fazer com um algoritmo simples de pesquisa linear, usando For, mas depois fiquei pensando que eu poderia melhorar o desempenho dessa pesquisa utilizando de outros algoritmos como o de pesquisa binária, mas não sei se é ideal pois para executar esse algortmo eu necessitaria ordenar a lista, então teria que usar dois algoritimos nessse caso que ficaria mais lento, então não sei se é melhor utilizar a busca linear mesmo ou fazer a ordenação e usar o pesquisa binária depois. Gostaria que algum dev mais experiênte pude-se me orientar.
não sei te ajudar, mas tenho a mesma duvida, compartilho meu obro para chorar junto com você!
Tabela? Tabela em banco de dados?
Se for banco de dados isso já tem neles!
Se for sei lá uma tabela simples em HTML Não precisaria se matar pra melhorar o algoritmo! Quase nada fara isso ser lento
Sim, é pre-requisito da busca binária que a lista em questão esteja ordenada.
Se não tiver como garantir que os elementos inseridos na lista sejam inseridos ordenados, provavelmente não vale apena ordenar e aplicar busca binária.
Mas vale a pena fazer uma análise. Encontrar um elemento em uma lista é O(n), enquanto a busca binária é (logn), um algoritmo de ordenação é de O(nlogn) ~ O(n²), dependendo de qual você esteja usando. Se tiver propriedades muito específicas você conseguiria ordenar até com O(n) com Radix Sort, mas não acho que seja o caso. Por fim, usar qualquer desses juntamente a busca binária daria O(logn + nlogn) que é O(nlogn), ou seja, ficaria melhor usar busca simples na lista.
Claro, tô imaginando o cenário mais simples possível pq você não falou muito, se por exemplo forem realizadas várias buscas consecutivas no mesmo array, ordenar e realizar apenas buscas binárias pode melhorar a performace.
Por fim, termino incentivando você a pesquisar um pouco mais antes de perguntar. Pois qualquer pesquisa rápida responderia que busca binária exige que a entrada esteja ordenada (Se não não dá para saber para qual lado deve ir).
Outra coisa, se a pesquisa está lenta, avalie se lista é a melhor estrutura de dados para o problema em questão.
Se for uma tabela HTML sugiro que dê uma olhada na lib datatables. Nela já tem várias funcionalidades como paginação, campo de busca, ordenação das colunas e várias outras coisas.
Mas se você só quer uma solução básica no HTML meio que a quantidade de dados pra deixar essa busca perceptivelmente lenta tem que ser muito grande. Então, se não for o caso, pode implantar usando um laço comum mesmo. As vezes a abordagem mais direta é a melhor.