Antes de compreender as diferenças entre a pesquisa linear e a binária, devemos primeiro conhecer a pesquisa linear e a pesquisa binária separadamente.

O que é uma pesquisa linear?

Uma pesquisa linear também é conhecida como pesquisa sequencial que simplesmente verifica cada elemento de cada vez. Suponha que queiramos pesquisar um elemento em um array ou lista; simplesmente calculamos seu comprimento e não saltamos em nenhum item.

Vamos considerar um exemplo simples.

Suponha que temos um array de 10 elementos conforme mostrado na figura abaixo:

A figura acima mostra uma matriz do tipo de caractere com 10 valores. Se quisermos pesquisar 'E', então a pesquisa começa a partir do 0^ºelemento e verifica cada elemento até que o elemento, ou seja, 'E' não seja encontrado. Não podemos pular diretamente do 0^ºelemento para o 4^ºelemento, ou seja, cada elemento é verificado um por um até que o elemento não seja encontrado.

Complexidade da pesquisa linear

À medida que a pesquisa linear verifica cada elemento, um por um, até que o elemento não seja encontrado. Se o número de elementos aumentar, o número de elementos a serem verificados também aumentará. Podemos dizer que o o tempo necessário para pesquisar os elementos é proporcional ao número de elementos . Portanto, a complexidade do pior caso é O(n)

O que é uma pesquisa binária?

Uma pesquisa binária é uma pesquisa em que o elemento do meio é calculado para verificar se é menor ou maior que o elemento a ser pesquisado. A principal vantagem de usar a pesquisa binária é que ela não verifica cada elemento da lista. Em vez de escanear cada elemento, ele realiza a busca até a metade da lista. Portanto, a pesquisa binária leva menos tempo para pesquisar um elemento em comparação com uma pesquisa linear.

Único pré-requisito da pesquisa binária é que um array deve estar em ordem classificada, enquanto a pesquisa linear funciona tanto em arrays classificados quanto em não classificados. O algoritmo de busca binária é baseado na técnica de dividir e conquistar, o que significa que dividirá o array recursivamente.

Existem três casos usados ​​na pesquisa binária:

Caso 1: dados

Caso 2: dados>a[mid] então right=mid-1

Caso 3: data = a[mid] // elemento é encontrado

No caso acima, ' a 'é o nome da matriz, meio é o índice do elemento calculado recursivamente, dados é o elemento que deve ser pesquisado, esquerda denota o elemento esquerdo da matriz e certo denota o elemento que ocorre no lado direito da matriz.

Vamos entender o funcionamento da pesquisa binária através de um exemplo.

Suponha que temos um array de tamanho 10 que é indexado de 0 a 9, conforme mostrado na figura abaixo:

Queremos pesquisar 70 elementos do array acima.

Passo 1: Primeiro, calculamos o elemento intermediário de um array. Consideramos duas variáveis, ou seja, esquerda e direita. Inicialmente, esquerda = 0 e direita = 9 conforme mostrado na figura abaixo:

O valor do elemento intermediário pode ser calculado como:

Portanto, mid = 4 e a[mid] = 50. O elemento a ser pesquisado é 70, então a[mid] não é igual a data. O caso 2 é satisfeito, ou seja, data>a[mid].

Passo 2: Como data>a[mid], então o valor de left é incrementado em mid+1, ou seja, left=mid+1. O valor de mid é 4, então o valor de left se torna 5. Agora, temos um subarray conforme mostrado na figura abaixo:

Agora, novamente, o valor médio é calculado usando a fórmula acima, e o valor de meio se torna 7. Agora, o meio pode ser representado como:

Na figura acima, podemos observar que a[mid]>data, então novamente, o valor de mid será calculado na próxima etapa.

Etapa 3: Como a[mid]>data, o valor de right é decrementado em mid-1. O valor de mid é 7, então o valor de right se torna 6. A matriz pode ser representada como:

O valor de mid será calculado novamente. Os valores da esquerda e da direita são 5 e 6, respectivamente. Portanto, o valor de mid é 5. Agora o mid pode ser representado em um array conforme mostrado abaixo:

Na figura acima, podemos observar que a[mid]

Passo 4: Como um [meio]

Agora o valor de mid é calculado novamente usando a fórmula que já discutimos. Os valores de esquerda e direita são 6 e 6 respectivamente, então o valor de mid torna-se 6 conforme mostrado na figura abaixo:

Podemos observar na figura acima que a[mid]=data. Portanto, a pesquisa é concluída e o elemento é encontrado com sucesso.

Diferenças entre pesquisa linear e pesquisa binária

A seguir estão as diferenças entre pesquisa linear e pesquisa binária:

Descrição

A pesquisa linear é uma pesquisa que encontra um elemento na lista pesquisando o elemento sequencialmente até que o elemento seja encontrado na lista. Por outro lado, uma pesquisa binária é uma pesquisa que encontra o elemento do meio na lista recursivamente até que o elemento do meio corresponda a um elemento pesquisado.

Funcionamento de ambas as pesquisas

A pesquisa linear começa a pesquisar a partir do primeiro elemento e examina um elemento por vez, sem pular para o próximo elemento. Por outro lado, a pesquisa binária divide o array ao meio calculando o elemento intermediário do array.

Implementação

A pesquisa linear pode ser implementada em qualquer estrutura de dados linear, como vetor, lista vinculada simples, lista vinculada dupla. Em contraste, a pesquisa binária pode ser implementada nessas estruturas de dados com travessia bidirecional, ou seja, travessia para frente e para trás.

Complexidade

A pesquisa linear é fácil de usar, ou podemos dizer que é menos complexa, pois os elementos para uma pesquisa linear podem ser organizados em qualquer ordem, enquanto que numa pesquisa binária, os elementos devem ser organizados numa ordem específica.

Elementos classificados

Os elementos para uma pesquisa linear podem ser organizados em ordem aleatória. Não é obrigatório na pesquisa linear que os elementos sejam organizados em ordem de classificação. Por outro lado, em uma pesquisa binária, os elementos devem ser organizados em ordem de classificação. Ele pode ser organizado em ordem crescente ou decrescente e, consequentemente, o algoritmo será alterado. Como a busca binária utiliza um array ordenado, é necessário inserir o elemento no local adequado. Em contraste, a pesquisa linear não necessita de um array ordenado, de modo que o novo elemento pode ser facilmente inserido no final do array.

Abordagem

A pesquisa linear usa uma abordagem iterativa para encontrar o elemento, por isso também é conhecida como abordagem sequencial. Em contraste, a pesquisa binária calcula o elemento intermediário da matriz, por isso usa a abordagem de dividir e conquistar.

Conjunto de dados

java faz loop while

A pesquisa linear não é adequada para grandes conjuntos de dados. Se quisermos pesquisar o elemento, que é o último elemento do array, uma pesquisa linear começará a pesquisar a partir do primeiro elemento e continuará até o último elemento, portanto o tempo necessário para pesquisar o elemento seria grande. Por outro lado, a pesquisa binária é adequada para um grande conjunto de dados, pois leva menos tempo.

Velocidade

Se o conjunto de dados for grande na pesquisa linear, o custo computacional será alto e a velocidade se tornará lenta. Se o conjunto de dados for grande na pesquisa binária, o custo computacional será menor em comparação com uma pesquisa linear e a velocidade se tornará rápida.

Dimensões

A pesquisa linear pode ser usada em arrays unidimensionais e multidimensionais, enquanto a pesquisa binária pode ser implementada apenas em arrays unidimensionais.

Eficiência

A pesquisa linear é menos eficiente quando consideramos grandes conjuntos de dados. A pesquisa binária é mais eficiente que a pesquisa linear no caso de grandes conjuntos de dados.

Vejamos as diferenças em forma tabular.