Pesquisa linear - Linear search

Pesquisa linear

Classe	Algoritmo de busca
Desempenho de pior caso	O ( n )
Melhor caso de desempenho	O (1)
Desempenho médio	O ( n / 2 )
Pior caso de complexidade de espaço	O (1) iterativo

Na ciência da computação , uma busca linear ou busca sequencial é um método para localizar um elemento em uma lista . Ele verifica sequencialmente cada elemento da lista até que uma correspondência seja encontrada ou toda a lista tenha sido pesquisada.

Uma pesquisa linear é executada no pior tempo linear e faz no máximo n comparações, onde n é o comprimento da lista. Se cada elemento tiver a mesma probabilidade de ser pesquisado, a pesquisa linear terá um caso médio de n + 1/2comparações, mas o caso médio pode ser afetado se as probabilidades de pesquisa para cada elemento variar. A pesquisa linear raramente é prática porque outros algoritmos e esquemas de pesquisa, como o algoritmo de pesquisa binária e tabelas de hash , permitem uma pesquisa significativamente mais rápida para tudo, exceto listas curtas.

Algoritmo

Uma pesquisa linear verifica sequencialmente cada elemento da lista até encontrar um elemento que corresponda ao valor de destino. Se o algoritmo atingir o final da lista, a pesquisa será encerrada sem sucesso.

Algoritmo básico

Dada uma lista L de n elementos com valores ou registos L ₀ .... L _{n -1} , e o valor alvo T , as seguintes sub-rotina usos linear pesquisa para encontrar o índice do alvo T em G .

1. Defina i como 0.
2. Se L _i = T , a pesquisa termina com sucesso; return i .
3. Aumente i em 1.
4. Se i < n , vá para a etapa 2. Caso contrário, a pesquisa será encerrada sem sucesso.

Com uma sentinela

O algoritmo básico acima faz duas comparações por iteração: uma para verificar se L _i é igual a T e a outra para verificar se i ainda aponta para um índice válido da lista. Ao adicionar um registro extra L _n à lista (um valor sentinela ) igual ao alvo, a segunda comparação pode ser eliminada até o final da busca, tornando o algoritmo mais rápido. A busca chegará à sentinela se o alvo não estiver contido na lista.

1. Defina i como 0.
2. Se L _i = T , vá para a etapa 4.
3. Aumente i em 1 e vá para a etapa 2.
4. Se i < n , a pesquisa termina com sucesso; return i . Caso contrário, a pesquisa termina sem sucesso.

Em uma mesa ordenada

Se a lista for ordenada de forma que L ₀ ≤ L ₁ ... ≤ L _{n −1} , a pesquisa pode estabelecer a ausência do alvo mais rapidamente, concluindo a pesquisa uma vez que L _i exceda o alvo. Essa variação requer uma sentinela maior que o alvo.

1. Defina i como 0.
2. Se L _i ≥ T , vá para a etapa 4.
3. Aumente i em 1 e vá para a etapa 2.
4. Se L _i = T , a pesquisa termina com sucesso; return i . Caso contrário, a pesquisa termina sem sucesso.

Análise

Para uma lista com n itens, o melhor caso é quando o valor é igual ao primeiro elemento da lista, caso em que apenas uma comparação é necessária. O pior caso é quando o valor não está na lista (ou ocorre apenas uma vez no final da lista), caso em que são necessárias n comparações.

Se o valor procurado ocorre k vezes na lista, e todas as ordens da lista são igualmente prováveis, o número esperado de comparações é

${\ displaystyle {\ begin {cases} n & {\ mbox {if}} k = 0 \\ [5pt] \ displaystyle {\ frac {n + 1} {k + 1}} & {\ mbox {if}} 1 \ leq k \ leq n. \ end {casos}}}$

Por exemplo, se o valor procurado ocorrer uma vez na lista e todas as ordens da lista forem igualmente prováveis, o número esperado de comparações é . No entanto, se for conhecido que ocorre uma vez, então no máximo n - 1 comparações são necessárias, e o número esperado de comparações é ${\ displaystyle {\ frac {n + 1} {2}}}$

${\ displaystyle \ displaystyle {\ frac {(n + 2) (n-1)} {2n}}}$

(por exemplo, para n = 2 este é 1, correspondendo a uma única construção if-then-else).

De qualquer maneira, assintoticamente o custo do pior caso e o custo esperado da pesquisa linear são ambos O ( n ).

Probabilidades não uniformes

O desempenho da pesquisa linear melhora se é mais provável que o valor desejado esteja próximo ao início da lista do que ao final. Portanto, se alguns valores são muito mais prováveis ​​de serem pesquisados ​​do que outros, é desejável colocá-los no início da lista.

Em particular, quando os itens da lista são organizados em ordem decrescente de probabilidade, e essas probabilidades são geometricamente distribuídas , o custo da pesquisa linear é apenas O (1).

Aplicativo

A pesquisa linear geralmente é muito simples de implementar e é prática quando a lista possui apenas alguns elementos ou ao realizar uma única pesquisa em uma lista não ordenada.

Quando muitos valores precisam ser pesquisados ​​na mesma lista, geralmente vale a pena pré-processar a lista para usar um método mais rápido. Por exemplo, pode-se classificar a lista e usar a pesquisa binária ou construir uma estrutura de dados de pesquisa eficiente a partir dela. Se o conteúdo da lista mudar com frequência, a reorganização repetida pode ser mais problemática do que compensadora.

Como resultado, embora em teoria outros algoritmos de pesquisa possam ser mais rápidos do que a pesquisa linear (por exemplo, pesquisa binária ), na prática, mesmo em matrizes de tamanho médio (cerca de 100 itens ou menos), pode ser inviável usar qualquer outra coisa. Em matrizes maiores, só faz sentido usar outros métodos de pesquisa mais rápidos se os dados forem grandes o suficiente, porque o tempo inicial para preparar (classificar) os dados é comparável a muitas pesquisas lineares.

Veja também

• Pesquisa ternária
• Tabela de hash
• Problema de pesquisa linear

Referências

Citações

Trabalho

• Knuth, Donald (1998). Classificando e pesquisando . The Art of Computer Programming . 3 (2ª ed.). Leitura, MA: Addison-Wesley Professional. ISBN  0-201-89685-0