Pesquisa linear vs pesquisa binária: diferença entre pesquisa linear e pesquisa binária

Publicados: 2021-02-09

Índice

Introdução

A alocação de memória contígua em linguagens de programação fornece uma implementação flexível de armazenamento de vários pontos de dados. Isso pode ser utilizado em seu pico se quisermos segregar os dados e mesclar todos os dados semelhantes em uma estrutura de dados contígua, como uma matriz, uma lista, etc.

A alocação de memória contígua tem muitas implementações em aplicações do mundo real, como um sistema operacional em computadores, sistemas de gerenciamento de banco de dados, etc. Essa estrutura de dados é considerada flexível porque adicionar um novo ponto de dados a uma matriz requer apenas uma única unidade de tempo, ou seja; O(1).

Mas o problema surge quando queremos examinar uma entrada específica ou procurar uma entrada específica porque todos os aplicativos do mundo real dependem dos comandos de acesso a dados. E essa tarefa deve ser rápida o suficiente para atender a velocidade do processador e da memória.

Existem vários algoritmos de pesquisa divididos com base no número de comparações que fazemos para pesquisar o elemento.

Se compararmos cada ponto de dados na matriz para pesquisar um elemento, isso será considerado uma pesquisa sequencial. Mas se estivermos comparando apenas alguns elementos pulando algumas das comparações, isso será considerado uma pesquisa de intervalo. Mas precisamos que um array esteja em ordem de classificação (ordem crescente ou decrescente) para realizar uma pesquisa de intervalo nele.

A complexidade de tempo da busca sequencial é linear O(n), e a complexidade de tempo da busca binária (um exemplo de busca de intervalo) é O(log n). Além disso, existem outros algoritmos de pesquisa, como pesquisa exponencial, pesquisa de salto, etc.

Mas a pesquisa linear e a pesquisa binária são usadas principalmente, onde a pesquisa linear é para dados aleatórios ou não classificados e a pesquisa binária é para dados classificados e ordenados. Hashing é um algoritmo de busca especial onde a complexidade de tempo de acesso a um ponto de dados é O(1).

Vamos primeiro percorrer os algoritmos de busca linear e busca binária e depois comparar as diferenças entre busca linear e busca binária.

Pesquisa linear

Como já discutido, o algoritmo de busca linear compara cada elemento no array, e aqui está o código para fazer isso.

classe pública UpGrad {
 public static int linear_search ( int [] arr, int n, int k){
 for ( int i= 0 ; i<n; i++)
 if (arr[i]==k)
 retorna i+ 1 ;
 retorno – 1 ;
 }
 public static void main (String[] args){
 int [] arr= new int []{ 1 , 2 , 5 , 6 , 3 , 8 , 9 , 9 , 0 , 13 , 45 , 65 };
 int k= 13 ;
 int n=arr.comprimento;
 int r=linear_search(arr, n, k);
 se (r==- 1 )
 System.out.println( “elemento não encontrado” );
 outro
 System.out.println( “elemento encontrado na posição “ +r+ ”” );
 }
 }

Vamos percorrer o código.

Declaramos uma função linear_search, que espera um array, chave inteira como parâmetros. Agora precisamos fazer um loop em todos os elementos e comparar se ele corresponde à nossa chave de pesquisa, então escrevemos um loop for que percorre o array e, dentro dele, há um loop if que verifica se o número nessa posição corresponde com a chave de pesquisa ou não. Se encontrarmos uma correspondência, devolveremos a posição. Se não houver tal elemento na matriz, retornaremos -1 no final da função.

Observe que, se tivermos várias aparições do mesmo número, retornaremos a posição de sua primeira ocorrência.

Chegando ao método main, declaramos e inicializamos um array inteiro. Então estamos inicializando a chave que deve ser pesquisada. Aqui estamos codificando a matriz e a chave, mas você pode alterá-la para a entrada do usuário. Agora que temos a lista de elementos e a chave a ser pesquisada, o método de pesquisa linear é chamado e o índice retornado é anotado. Posteriormente estamos verificando o valor retornado e imprimindo o índice se a chave existir, senão imprimindo chave não encontrada.

Pesquisa binária

A pesquisa binária é mais otimizada do que a pesquisa linear, mas a matriz deve ser classificada para aplicar a pesquisa binária. E aqui está o código para fazer isso.

classe pública UpGrad {
 public static int binary_search ( int [] arr, int k){
 int l= 0 ,h=arr.length- 1 ,mid= 0 ;
 enquanto (l<=h){
 meio=l+(hl)/ 2 ;
 if (arr[mid]==k)
 retornar meio + 1 ;
 senão se (arr[mid]>k)
 h=meio- 1 ;
 outro
 l=meio+ 1 ;
 }
 retorno – 1 ;
 }
 public static void main (String[] args){
 int [] arr= new int []{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 };
 int k= 8 ;
 int r=binary_search(arr,k);
 se (r==- 1 )
 System.out.println( “elemento não encontrado” );
 outro
 System.out.println( “elemento encontrado na posição “ +r+ ”” );
 }
 }

Vamos percorrer o código.

Declaramos um método binary_search que espera um array de inteiros ordenados e uma chave de inteiros como parâmetros. Estamos inicializando as variáveis ​​baixa, alta, média. Aqui baixo, alto são ponteiros onde baixo estará no índice 0 e alto estará no índice n no início. Então, como funciona a pesquisa binária?

No início, vamos calcular o médio de baixo e alto. Podemos calcular o médio como (baixo + alto)/2, mas às vezes o alto pode ser um número grande, e adicionar baixo ao alto pode levar a um estouro de número inteiro. Portanto, calcular mid como low+(high-low)/2 seria uma maneira ideal.

Compararemos o elemento no meio com a chave de pesquisa e retornaremos o índice se encontrarmos uma correspondência. Caso contrário, verificaremos se o elemento mid é maior que a chave ou menor que a chave. Se o mid for maior, precisamos verificar apenas a primeira metade do array porque todos os elementos na segunda metade do array são maiores que a chave, então atualizaremos o high para mid-1.

Da mesma forma, se mid for menor que key, precisamos pesquisar na segunda metade da matriz, atualizando o low para mid+1. Lembre-se de que a busca binária é baseada no algoritmo de diminuição e conquista, pois estamos ignorando uma das metades do array em cada iteração.

Voltando ao nosso código, construímos o método main. Inicializou uma matriz ordenada e uma chave de pesquisa, fez uma chamada para a pesquisa binária e imprimiu os resultados.

Agora que percorremos os algoritmos da pesquisa linear e da pesquisa binária, vamos comparar os dois algoritmos.

Pesquisa linear vs pesquisa binária

Trabalhando

  • A pesquisa linear itera por todos os elementos e os compara com a chave que deve ser pesquisada.
  • A pesquisa binária diminui sabiamente o tamanho da matriz que deve ser pesquisada e compara a chave com o elemento médio todas as vezes.

Estrutura de dados

  • A pesquisa linear é flexível com todas as estruturas de dados, como uma matriz, lista, lista vinculada, etc.
  • A pesquisa binária não pode ser realizada em todas as estruturas de dados, pois precisamos de travessia multidirecional. Portanto, estruturas de dados como a lista encadeada única não podem ser usadas.

Pré-requisitos

  • A busca linear pode ser realizada em todos os tipos de dados, os dados podem ser aleatórios ou ordenados, o algoritmo permanece o mesmo. Portanto, não há necessidade de qualquer pré-trabalho a ser feito.
  • A pesquisa binária funciona apenas em uma matriz classificada. Portanto, classificar uma matriz é um pré-requisito para esse algoritmo.

Caso de uso

  • A pesquisa linear é geralmente preferida para conjuntos de dados menores e ordenados aleatoriamente.
  • A pesquisa binária é preferida para conjuntos de dados comparativamente maiores e classificados.

Eficácia

  • A pesquisa linear é menos eficiente no caso de conjuntos de dados maiores.
  • A pesquisa binária é mais eficiente no caso de conjuntos de dados maiores.

Complexidade de tempo

  • Na busca linear, a complexidade do melhor caso é O(1) onde o elemento é encontrado no primeiro índice. A complexidade do pior caso é O(n) onde o elemento é encontrado no último índice ou o elemento não está presente na matriz.
  • Na busca binária, a complexidade do melhor caso é O(1), onde o elemento é encontrado no índice do meio. A complexidade do pior caso é O( log 2 n).

Funcionamento a seco

Vamos supor que temos um array de tamanho 10.000.

  • Em uma busca linear, a complexidade do melhor caso é O(1) e a complexidade do pior caso é O(10000).
  • Em uma busca binária, a complexidade do melhor caso é O(1) e a complexidade do pior caso é O( log 2 10000)=O(13.287).

Conclusão

Entendemos a importância do acesso a dados em arrays, entendemos algoritmos de busca linear e busca binária. Percorreu os códigos de busca linear e busca binária. Comparou as diferenças entre a pesquisa linear e a pesquisa binária, fez uma simulação para um exemplo de grande porte.

Agora que você está ciente das diferenças entre pesquisa linear e pesquisa binária, tente executar os dois códigos para um grande conjunto de dados sied e compare o tempo de execução, comece a explorar diferentes algoritmos de pesquisa e tente implementá-los!

Se você está curioso para aprender sobre ciência de dados, confira o PG Diploma in Data Science do IIIT-B & upGrad, que é criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com especialistas do setor, 1- on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.

Aprenda cursos de ciência de dados online das melhores universidades do mundo. Ganhe Programas PG Executivos, Programas de Certificado Avançado ou Programas de Mestrado para acelerar sua carreira.

Compare a pesquisa linear e a pesquisa binária usando suas complexidades.

A Pesquisa Binária é mais otimizada e eficiente que a Pesquisa Linear de várias maneiras, especialmente quando os elementos estão em ordem de classificação. A razão se resume às complexidades de ambas as buscas.
Pesquisa linear
1. Complexidade de Tempo: O(N) - Como na busca linear, percorremos o array para verificar se algum elemento corresponde à chave. Na pior das hipóteses, o elemento estará presente no final do array, então temos que atravessar até o final e, portanto, a complexidade de tempo será O(N) onde N é o número total de elementos do array.
2. Complexidade do Espaço: O(1) - Não estamos usando nenhum espaço extra, então a complexidade do espaço será O(1).
Pesquisa binária
1. Complexidade de Tempo: O(log N) - Na Busca Binária, a busca é reduzida pela metade, pois só temos que olhar para o meio do array. E estamos constantemente encurtando nossa busca para o meio da seção onde o elemento está presente.
2. Complexidade Espacial: O(1)
- Não estamos usando nenhum espaço extra, então a complexidade do espaço será O(1).

Existe algum outro método para pesquisar um elemento em uma matriz?

Embora a busca linear e a busca binária sejam frequentemente usadas para busca, de fato existe outro método de busca – o método de interpolação. É uma versão otimizada do Binary Search onde todos os elementos são distribuídos uniformemente.
A ideia por trás desse método é que, na busca binária, sempre olhamos para o meio do array. Mas neste método, a pesquisa pode ir para locais diferentes dependendo de onde a chave está localizada. Por exemplo, se a chave estiver localizada perto do último elemento da matriz, a pesquisa começará no final da matriz.

Quais são as diferentes complexidades de tempo da pesquisa de interpolação?

A complexidade de tempo do pior caso da pesquisa de interpolação é O(N), pois no pior caso, a chave estará no final da matriz, de modo que o iterador precisa percorrer toda a matriz.
A complexidade média do caso será O(log(log N) já que o elemento pode estar em qualquer lugar do array, ou próximo ao ponto de partida também.
A complexidade do melhor caso será O(1), pois, no melhor caso, a chave será o primeiro elemento da matriz.