Em informática , um algoritmo de busca é um tipo de algoritmo que, para um domínio, um problema desse domínio e dados critérios, retorna como resultado um conjunto de soluções respondendo ao problema.
Suponha que o conjunto de suas entradas seja divisível em um subconjunto, com respeito a um determinado critério, que pode ser, por exemplo, uma relação de ordem . Em geral, tal algoritmo verifica um certo número dessas entradas e retorna uma ou mais das entradas desejadas como saída.
O conjunto de todas as soluções potenciais no campo é chamado de espaço de busca .
Em estruturas de dados usuais, como listas , tabelas ou árvores , existem algoritmos bem conhecidos que podem ser facilmente implementados e que exploram as propriedades da estrutura de dados.
Um exemplo clássico é a busca dicotômica, onde o espaço de busca é dividido em dois em cada tentativa, o que dá complexidade logarítmica (portanto, muito vantajoso). Dois outros exemplos são a pesquisa sequencial e a pesquisa por interpolação .
Para problemas complexos, encontrar soluções é uma questão de inteligência artificial .
Esses algoritmos estão no centro de questões importantes na complexidade algorítmica. Eles também são muito importantes devido aos seus amplos campos de aplicação.