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, ao mesmo tempo que se verifica se existe o valor pretendido.

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, 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

Falso e mudará para Verdadeiro quando o valor desejado for encontrado.

Veja a implementação Python abaixo como exemplo:

def linearSearch (mylist, item):

encontrado = falso

índice = 0

while index

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.

Relacionado: O que é notação Big-O?

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.

Relacionado: O que é recursão e como usá-la?

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

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 caindo 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.

Como usar a classificação por seleção

A classificação por seleção é um pouco difícil de entender para iniciantes, mas não é muito desafiador depois que você entende as coisas.

Leia a seguir

Sobre o autor