Pesquisa Linear

Podemos definir o problema da pesquisa linear (ou pesquisa sequencial) como a seguir:

  • Descrição da entrada: Uma sequência $S$ de $n$ números e um elemento desejado $e$.

  • Descrição da tarefa: Determinar se o elemento $e$ está na sequência $S$

  • Descrição da saída: Se o elemento estiver na sequência, retorne o índice em que o elemento $e$ aparece em $S$. Caso contrário, retorne o valor $-1$.

Na pesquisa sequencial, começamos da frente (início) do vetor (ou lista) de elementos e comparamos cada um dos elementos com o elemento desejado até encontrarmos uma correspondência (o elemento está presente) ou atingimos o final da lista (o elemento não está presente). Vejamos um exemplo.

def pesquisa_linear(arranjo, elemento_desejado):
    for elemento in arranjo:
        if elemento == elemento_desejado:
            print("Elemento {} está presente no arranjo.".format(elemento_desejado))
            return
    print("Elemento {} não está presente no arranjo.".format(elemento_desejado))


arranjo = list(range(1, 100))

# Pesquisa por elemento presente.
pesquisa_linear(arranjo, 83)

# Pesquisa por elemento ausente.
pesquisa_linear(arranjo, 200)
Elemento 83 está presente no arranjo.
Elemento 200 não está presente no arranjo.

A pesquisa linear, como o próprio nome sugere, possui complexidade linear ($O(n)$) no número de elementos do vetor, no pior caso. No melhor caso, o elemento desejado se encontra na primeira (ou nas primeiras posições do vetor), e o algoritmo precisa fazer apenas umas poucas comparações. Note que em nossa implementação, quando encontramos um elemento, saímos imediatamente da função, pois não é necessário continuar percorrendo o restante do vetor quando já sabemos que o elemento está presente.

Para reforçar o funcionamento do algoritmo, vejamos uma animação de uma pesquisa por um elemento (o número 7) em um arranjo de inteiros.

Pesquisa Linear

Pesquisa Linear em Python

Em Python, é muito fácil fazer pesquisa linear em uma lista de elementos. Existem várias formas de se fazer isso, na verdade, e aqui vamos explicar duas: primeiro, usando o operador in, e depois usando o método index(). Veja abaixo um exemplo de como implementar pesquisa linear usando o operador in.

def pesquisa_linear_in(arranjo, item):
    return item in arranjo

arranjo = list(range(1, 100))

# Pesquisa por elemento presente.
print("O elemento {} está presente no arranjo? {}".format(83, pesquisa_linear_in(arranjo, 83)))

# Pesquisa por elemento ausente.
print("O elemento {} está presente no arranjo? {}".format(200, pesquisa_linear_in(arranjo, 200)))
O elemento 83 está presente no arranjo? True
O elemento 200 está presente no arranjo? False

Note que nossa implementação acima simplesmente diz se o elemento desejado está ou não presente na lista de entrada. Entretanto, há situações em que desejamos saber, se o elemento estiver presente, em qual índice o elemento está na lista. Para isso, usaremos o método index(), como mostrado a seguir.

def pesquisa_linear_index(arranjo, item):
    try:
        return arranjo.index(item)
    except ValueError:
        return -1

arranjo = list(range(1, 100))

# Pesquisa por elemento presente.
print("O elemento {} está no índice {} do arranjo.".format(83, pesquisa_linear_index(arranjo, 83)))

# Pesquisa por elemento ausente.
print("O elemento {} está no índice {} do arranjo.".format(200, pesquisa_linear_index(arranjo, 200)))
O elemento 83 está no índice 82 do arranjo.
O elemento 200 está no índice -1 do arranjo.

Perceba usamos um recurso novo (try/except) na função pesquisa_linear_index(). Fizemos isso porque o método index() retorna o índice em que o elemento aparece na lista de entrada (caso esse elemento esteja presente) e ValueError caso o elemento não esteja na lista.

Em Python, usamos o recurso try/except para tratar exceções. Veja este link para uma explicação mais detalhada sobre esse assunto.

Uma pergunta natural a se fazer é: existe alguma forma de se pesquisar por um elemento em um arranjo de modo mais eficiente?

A resposta a essa pergunta depende da forma como os elementos estão organizados no vetor. Se eles não estiverem em uma ordem específica, não há como fugir da pesquisa linear. Se os elementos estiverem ordenados de alguma forma, podemos usar pesquisa binária.

Playground

# Use este espaço para praticar o que você aprendeu nesta seção. # Basta digitar o código no espaço abaixo e clicar 'run'.
Anterior Início Próximo