Algoritmos de pesquisa linear e binária explicados
A capacidade de pesquisar alguns dados é um aspecto importante da ciência da computação. Os algoritmos de pesquisa são usados para procurar um item específico em um conjunto de dados.
Os algoritmos retornam um resultado booleano (verdadeiro ou falso) para uma consulta de pesquisa. Eles também podem ser modificados para fornecer a posição relativa do valor encontrado.
Para este artigo, os algoritmos se concentrarão em determinar se um valor existe.
Algoritmos de pesquisa linear
A pesquisa linear também é conhecida como pesquisa sequencial. Neste tipo de pesquisa, cada valor de uma lista é visitado um a um de forma ordenada enquanto se verifica se existe o valor desejado.
O algoritmo verifica valor por valor até encontrar o valor que você está procurando ou ficar sem valores para pesquisar. Quando os valores a serem pesquisados acabam, isso significa que sua consulta de pesquisa não existe na lista.
Um algoritmo de busca sequencial leva em uma lista de valores e o item desejado na lista como seus parâmetros. O resultado de retorno é inicializado como False e mudará para True quando o valor desejado for encontrado.
Veja a implementação Python abaixo como exemplo:
def linearSearch (mylist, item):
encontrado = falso
índice = 0
while index <len (mylist) e não encontrado:
if mylist [index] == item:
encontrado = verdadeiro
outro:
índice = índice + 1
retorno encontrado
Análise de Algoritmo
O melhor cenário ocorre quando o item desejado é o primeiro da lista. O pior caso ocorre quando o item desejado é o último da lista (o enésimo item). Portanto, a complexidade de tempo para pesquisa linear é O (n).
O cenário de caso médio no algoritmo acima é n / 2.
Pesquisa Linear Modificada
É importante saber que o algoritmo usado assume que uma lista aleatória de itens é fornecida a ele. Ou seja, os itens da lista não estão em uma ordem específica.
Suponha que os itens estejam em uma ordem específica, digamos do menor para o maior. Seria possível obter alguma vantagem em computação.
Tome um exemplo de busca de 19 na lista fornecida: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Após completar 23 anos, ficaria claro que o item procurado não existe na lista. Portanto, não seria mais importante continuar pesquisando o restante dos itens da lista.
Algoritmos de pesquisa binários
Você viu como uma lista ordenada pode reduzir o cálculo necessário. O algoritmo de pesquisa binária aproveita ainda mais essa eficiência do que apresentar uma lista ordenada.
O algoritmo começa pegando um valor médio de uma lista ordenada e verificando se é o valor desejado. Se não for, o valor é verificado se é menor ou maior do que o valor desejado.
Se for menor, não há necessidade de verificar a metade inferior da lista. Caso contrário, se for maior, passa para a metade superior da lista.
Independentemente da sublista (esquerda ou direita) escolhida, o valor do meio será novamente determinado. O valor é verificado novamente se for o valor necessário. Caso contrário, é verificado se é menor ou maior que o valor solicitado.
Este processo é repetido até que um valor seja encontrado, se estiver lá.
A implementação Python abaixo é para o algoritmo de pesquisa binária.
def binarySearch (mylist, item):
baixo = 0
alta = len (minha lista) – 1
encontrado = falso
enquanto baixo <= alto e não encontrado:
mid = (baixo + alto) // 2
if mylist [mid] == item:
encontrado = verdadeiro
elif item <mylist [mid]:
alto = médio – 1
outro:
baixo = médio + 1
retorno encontrado
Análise de Algoritmo
O melhor cenário ocorre quando o item desejado é considerado o item do meio. O pior cenário não é tão simples. Siga a análise abaixo:
Após a primeira comparação, n / 2 itens serão deixados. Após o segundo, n / 4 itens serão deixados. Após o terceiro, n / 8.
Observe que o número de itens continua diminuindo pela metade até atingir n / 2i, onde i é o número de comparações. Depois de toda a divisão, ficamos com apenas 1 item.
Isso implica:
n / 2i = 1
Portanto, a pesquisa binária é O (log n).
Seguindo para a classificação
Na pesquisa binária, consideramos um caso em que o array fornecido já estava ordenado. Mas suponha que você tenha um conjunto de dados não ordenado e queira realizar uma pesquisa binária nele. O que você faria?
A resposta é simples: classifique. Existem várias técnicas de classificação na ciência da computação que foram bem pesquisadas. Uma dessas técnicas que você pode começar a estudar é o algoritmo de classificação de seleção, embora também tenhamos muitos guias relacionados a outras áreas.
