Introdução ao algoritmo de pesquisa linear: introdução e recursos [com exemplos]

Publicados: 2021-06-22

Índice

O que é Pesquisar?

A pesquisa é o processo de encontrar um determinado elemento em uma lista de elementos. Ele ajuda na busca de um determinado registro. Portanto, é uma técnica de identificação do local de um determinado item. O sucesso de um processo de busca depende se o item a ser pesquisado foi identificado ou não.

A estrutura Data permite a busca de dados através de dois métodos.

  1. Pesquisa linear ou pesquisa sequencial
  2. Pesquisa binária

Pesquisa linear

Algoritmos de busca linear são um tipo de algoritmo para busca sequencial dos dados. Este algoritmo encontra um dado elemento com complexidade O(n). É aplicado a uma coleção de itens. Cada item dos dados é pesquisado sequencialmente e retornado se corresponder ao elemento pesquisado. Se nenhuma correspondência for encontrada, a pesquisa continua até o final dos dados coletados. É basicamente uma técnica de explorar cada elemento enquanto percorre a lista. O algoritmo de busca pode ser aplicado tanto aos dados ordenados como aos não ordenados. A pesquisa praticamente linear raramente é usada devido às opções de pesquisa mais rápidas fornecidas por outros algoritmos de pesquisa, como algoritmos de pesquisa binária e tabelas de hash.

Etapas no algoritmo de busca linear

  • Leitura do elemento de pesquisa pelo usuário.
  • O elemento a ser pesquisado é compactado com o primeiro elemento da lista.
  • Se os elementos corresponderem, um retorno será gerado.
  • Se os elementos não corresponderem, o elemento a ser pesquisado será comparado ao segundo elemento da lista.
  • O processo é repetido até que o elemento seja correspondido.

Recursos de algoritmos de busca linear

  1. Geralmente é aplicado a uma pequena lista de dados não ordenados ou não ordenados.
  2. O tempo é linearmente dependente do número de elementos, portanto, tem uma complexidade de tempo se O(n).
  3. A implementação é muito simples.

Algoritmos de busca linear

Um método de loop contínuo continua a menos que e até que o item seja encontrado

  • algoritmo Seqnl_Search(lista, item)
  • Pré: lista != ;
  • Post: retorna o índice do item se encontrado, caso contrário: 1
  • índice <- fi
  • while index < list.Cnt e list[index] != item //cnt: variável do contador
  • índice <- índice + 1
  • terminar enquanto
  • if index < list.Cnt e list[index] = item
  • índice de retorno
  • fim se
  • retorno: 1
  • fim Seqnl_Search

Exemplo de pesquisa linear

Problema: Dado um array arr[] de n elementos, escreva uma função para buscar um dado elemento x em arr[].

Figura 1: Um exemplo de código mostrando a implementação do algoritmo de busca linear

Fonte

Algoritmos de busca linear podem ser usados ​​em várias linguagens de programação.

  1. Pesquisa linear em Python

Figura 2: um exemplo de código mostrando um algoritmo de pesquisa linear na linguagem Python

Fonte

Saída: O elemento está presente no índice 3

  1. Pesquisa linear em C

Figura 3: Um exemplo de código mostrando um algoritmo de busca linear na linguagem C

Fonte

Saída : O elemento está presente no índice 3

  1. Pesquisa linear na estrutura de dados

O pseudocódigo para um problema de busca linear em estrutura de dados é

Figura 4: O pseudocódigo para algoritmo de busca linear

Fonte

Pesquisa binária

A pesquisa binária é um algoritmo para pesquisar elementos em uma matriz de elementos. Comparado com o algoritmo de busca linear, o algoritmo de busca binária é aplicado a uma lista ordenada de dados.

O algoritmo de pesquisa binária inclui as seguintes etapas

  • Comparação do elemento a ser pesquisado com o elemento do meio da lista ou array.
  • Se o elemento corresponder ao elemento da lista, ele retornará o índice do elemento do meio.
  • Se nenhuma correspondência for retornada, será verificado se o elemento é maior ou menor que o elemento do meio.
  • Para um elemento de valor maior que o elemento do meio, a pesquisa é realizada no lado direito da matriz.
  • Da mesma forma, se o elemento for menor em valor do que o elemento do meio, a pesquisa será realizada no lado esquerdo da lista.

Portanto, a pesquisa binária é melhor aplicada quando os dados contêm um grande número de elementos de haste de maneira ordenada. Isso torna um requisito para o algoritmo de pesquisa que a lista/array seja classificada.

Recursos da Pesquisa Binária

  • O algoritmo de pesquisa binária é útil para pesquisar um grande número de elementos em uma matriz.
  • O algoritmo de busca binária tem uma complexidade de tempo de O(logn).
  • A implementação de um algoritmo de busca binária é simples.

Algoritmo de Pesquisa Binária

  • Algoritmo Binary_Search(lista, item)
  • Defina L para 0 e R para n: 1
  • se L > R, então Binary_Search termina como malsucedido
  • outro
  • Defina m (a posição no elemento intermediário) para o piso de (L + R) / 2
  • se Am < T, defina L para m + 1 e vá para o passo 3
  • se Am > T, defina R para m: 1 e vá para o passo 3
  • Agora, Am = T,
  • a pesquisa é feita; retorno (m)

Conclusão

Neste artigo, analisamos o que é um Algoritmo de Pesquisa Linear e também estudamos em detalhes como pesquisar um determinado elemento de uma lista usando o Algoritmo de Pesquisa Linear. Por fim, também vimos como poderíamos implementar praticamente o Algoritmo de Pesquisa Linear usando Python 3 como linguagem e obter a saída desejada.

Se você estiver interessado em Ciência de Dados, você deve conferir o Programa PG Executivo em Ciência de Dados do IIIT-B e do upGrad, que foi cuidadosamente elaborado para profissionais que trabalham e oferece vários estudos de caso, workshops práticos, orientação individual e muito mais.

Como a pesquisa linear é diferente da pesquisa binária?

O seguinte ilustra as principais diferenças entre a pesquisa linear e a pesquisa binária:
 Pesquisa linear -
 1. Os elementos não precisam estar em nenhuma ordem específica para busca linear.
 2. Na pesquisa linear, os elementos são acessados ​​sequencialmente.
 3. O(n), onde n é o número de elementos da matriz.
 4. A Pesquisa Linear é preferida quando o conjunto de dados é relativamente menor.
 Pesquisa Binária -
 1. Os elementos devem ser classificados para pesquisa binária.
 2. Os elementos são acessados ​​aleatoriamente na busca binária.
 3. O(log n), onde n é o número de elementos do array.
 4. A Pesquisa Binária é geralmente preferível para um conjunto de dados maior.

Quais são as aplicações da busca linear?

A seguir estão algumas das aplicações significativas da pesquisa linear:
 A pesquisa linear é eficiente para pesquisar em conjuntos de dados com um número menor de elementos. Se apenas uma única pesquisa for necessária para ser realizada em dados não ordenados, a pesquisa linear é preferível a outros algoritmos de pesquisa.
 A busca de um nó em uma lista encadeada torna-se eficiente quando uma busca linear é realizada. Além disso, a pesquisa binária e a pesquisa linear têm a mesma complexidade de tempo em listas vinculadas. A Pesquisa Binária pode até ficar complexa para realizar operações de pesquisa em listas vinculadas.
 Se os elementos no conjunto de dados forem modificados repetidamente, nesses casos, a pesquisa linear é a escolha preferida.

Dê exemplos em que a pesquisa linear pode ser vista na vida real?

O algoritmo de busca linear é análogo à busca na vida real. Existem vários exemplos que comprovam isso:
 Procurando um livro em uma pilha de 100 livros. Você digitalizará linearmente o nome de cada livro até encontrar o correto
 Encontrar seu táxi no estacionamento. Quando você reserva uma corrida de táxi, você tem o número da placa do táxi. Para encontrar seu táxi, o método óbvio seria combinar a placa de cada carro com o seu número.
 Encontrando seus biscoitos favoritos nas prateleiras das lojas. De uma enorme coleção de cookies em uma loja, você pesquisará cada linha, uma por uma.