o principal diferença entre a pesquisa linear e a pesquisa binária é que uma pesquisa binária (também conhecida como pesquisa de meio intervalo ou pesquisa logarítmica) é mais eficiente e leva menos tempo para pesquisar um elemento do que uma pesquisa linear (ou pesquisa sequencial).

Pesquisar é uma operação que permite localizar um elemento em uma estrutura de dados específica, como uma matriz. Existem dois tipos de pesquisa: pesquisa linear e pesquisa binária. A pesquisa linear verifica os elementos de uma matriz um por um em ordem sequencial para descobrir se o item necessário está presente na matriz. Por outro lado, a pesquisa binária é um algoritmo mais eficiente do que a pesquisa linear, pois pesquisa o item comparando-o com o elemento do meio.

Pesquisa binária, pesquisa linear, algoritmo de pesquisa

O que é pesquisa linear

A pesquisa linear é um algoritmo de pesquisa simples. Aqui, a busca ocorre de um item após o outro. Isso é; este algoritmo verifica cada item e verifica se há um item correspondente daquele. Se o item não estiver presente, a pesquisa continua até o final dos dados. Portanto, a busca linear é um algoritmo que permite percorrer cada elemento de um array para localizar o item determinado.

Em uma pesquisa linear, o consumo de tempo ou o número de comparações para pesquisar um elemento ajuda a determinar a eficiência do algoritmo. Se o elemento que procuramos estiver na primeira posição da estrutura de dados, ele requer apenas uma comparação. Quando o elemento necessário está na última posição, é necessário um número N de comparações para encontrar o elemento. Aqui, o N se refere ao número de itens de dados.

O que é pesquisa binária

A pesquisa binária é um algoritmo rápido. Porém, é necessário classificar os itens de dados antes de realizar uma pesquisa binária. Ele encontra o item comparando o item mais central da coleção. Portanto, a pesquisa binária leva menos tempo para pesquisar um determinado item com menos número de comparações, pois envolve encontrar o elemento do meio e comparar o elemento do meio com o elemento a ser pesquisado.

Em uma pesquisa binária, se o elemento do meio for o elemento necessário, esse índice retorna. Se o item do meio for superior ao item pesquisado, o item pesquisado estará na submatriz esquerda do item do meio. Caso contrário, os itens estão na submatriz direita do item do meio. E, este processo continua no subarray até que o tamanho do subarray se torne zero. Nesse algoritmo, o número de itens a pesquisar diminui a cada vez.

Diferença entre pesquisa linear e pesquisa binária

Definição

A pesquisa linear é um algoritmo para encontrar um elemento em uma lista verificando sequencialmente os elementos da lista até encontrar o elemento correspondente. A pesquisa binária é um algoritmo que encontra a posição de um valor de destino em uma matriz classificada. Portanto, esta é a principal diferença entre a pesquisa linear e a pesquisa binária.

Sinônimos

A pesquisa sequencial é outro termo para pesquisa linear, enquanto a pesquisa de meio intervalo ou pesquisa logarítmica se refere à mesma pesquisa binária.

Complexidade de tempo

A complexidade de tempo de uma pesquisa linear é O (N) enquanto a complexidade de tempo de uma pesquisa binária é O (log₂N). Portanto, esta é outra diferença entre a pesquisa linear e a pesquisa binária.

Melhor caso

Além disso, o melhor caso em uma pesquisa linear é encontrar o elemento na primeira posição, enquanto o melhor caso em uma pesquisa binária é encontrar o elemento na posição intermediária.

Classificando o Array

Em uma pesquisa linear, não é necessário classificar a matriz antes de pesquisar o elemento. No entanto, em uma pesquisa binária, é necessário classificar o array antes de pesquisar o elemento. Portanto, o pré-requisito para classificar o array faz a diferença entre a pesquisa linear e a pesquisa binária.

Eficiência

Uma outra diferença entre a pesquisa linear e a pesquisa binária é sua eficiência. A pesquisa binária é mais eficiente do que a pesquisa linear.

Simplicidade

Além disso, a pesquisa binária é mais complexa do que a pesquisa linear.

Conclusão

A pesquisa linear e a pesquisa binária são dois algoritmos para pesquisar um elemento em uma estrutura de dados, como uma matriz. A pesquisa binária é eficiente e rápida do que a pesquisa linear, mas é obrigatório classificar a matriz antes de realizar a operação de pesquisa. Assim, a principal diferença entre a busca linear e a busca binária é que a busca binária é mais eficiente e leva menos tempo para buscar um elemento, quando comparada à busca linear.

Referência:

1. “Pesquisa Linear.” Wikipedia, Wikimedia Foundation, 13 de dezembro. Disponível aqui.2. “Algoritmo de pesquisa binária.” Wikipedia, Wikimedia Foundation, 26 de dezembro de 2018, disponível aqui.

Cortesia de imagem:

1. “Pesquisa binária em array” Por Tushe2000 - Predefinição: LoStrangolatore (Domínio Público) via Commons Wikimedia