A principal diferença entre a pesquisa linear e a pesquisa binária é que a pesquisa binária leva menos tempo para pesquisar um elemento da lista classificada de elementos. Assim, infere-se que a eficiência do método de pesquisa binária é maior que a pesquisa linear.
Outra diferença entre os dois é que há um pré-requisito para a pesquisa binária, ou seja, os elementos devem ser classificados, enquanto na pesquisa linear não existe tal pré-requisito. Embora ambos os métodos de busca usem técnicas diferentes que são discutidas abaixo.
Gráfico de comparação
| Base para comparação | Pesquisa linear | Pesquisa binária |
|---|---|---|
| Complexidade do Tempo | EM) | O (log 2 N) |
| Melhor tempo de caso | Primeiro Elemento O (1) | Elemento central O (1) |
| Pré-requisito para um array | Não exigido | Matriz deve estar em ordem de classificação |
| Pior caso para N número de elementos | N comparações são necessárias | Pode concluir depois de apenas comparações log 2 N |
| Pode ser implementado em | Lista Array e Linked | Não pode ser implementado diretamente na lista vinculada |
| Inserir operação | Facilmente inserido no final da lista | Exigir o processamento para inserir no seu devido lugar para manter uma lista ordenada. |
| Tipo de algoritmo | Iterativo na natureza | Divida e conquiste na natureza |
| Utilidade | Fácil de usar e sem necessidade de elementos encomendados. | De qualquer forma, algoritmos e elementos complicados devem ser organizados em ordem. |
| Linhas de código | Menos | Mais |
Definição de pesquisa linear
Em uma pesquisa linear, cada elemento de uma matriz é recuperado um a um em uma ordem lógica e verificado se é um elemento desejado ou não. Uma pesquisa não será bem-sucedida se todos os elementos forem acessados e o elemento desejado não for encontrado. Na pior das hipóteses, o número de casos médios pode ter que varrer metade do tamanho da matriz (n / 2).
Portanto, a pesquisa linear pode ser definida como a técnica que percorre o array seqüencialmente para localizar o item fornecido. O programa abaixo ilustra a busca de um elemento da matriz usando a pesquisa.
Eficiência de busca linear
O consumo de tempo ou o número de comparações feitas na pesquisa de um registro em uma tabela de pesquisa determina a eficiência da técnica. Se o registro desejado estiver presente na primeira posição da tabela de pesquisa, somente uma comparação será feita. Quando o registro desejado é o último, então n comparações devem ser feitas. Se o registro estiver presente em algum lugar na tabela de pesquisa, em média, o número de comparações será (n + 1/2). A pior eficiência da técnica é O (n) significa a ordem de execução.
C Programa para procurar um elemento com técnica de busca linear.
#include #include void main () {int um [100], n, i, item, loc = -1; clrscr (); printf ("\ nDigite o número do elemento:"); scanf ("% d", & n); printf ("Digite os números: \ n"); para (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nDigite o número a ser pesquisado:"); scanf ("% d", & item); para (i = 0; i = 0) {printf ("\ n% d é encontrado na posição% d:", item, loc + 1); } else {printf ("\ n item não existe"); } getch (); } Definição de pesquisa binária
Pesquisa binária é um algoritmo extremamente eficiente. Essa técnica de pesquisa consome menos tempo na pesquisa do item determinado em comparações mínimas possíveis. Para fazer a pesquisa binária, primeiro temos que ordenar os elementos da matriz.
A lógica por trás dessa técnica é dada abaixo:
- Primeiro, encontre o elemento do meio do array.
- O elemento do meio da matriz é comparado ao elemento a ser pesquisado.
Existem três casos que podem surgir:
- Se o elemento for o elemento necessário, a pesquisa será bem-sucedida.
- Quando o elemento for menor que o item desejado, pesquise apenas a primeira metade da matriz.
- Se for maior que o elemento desejado, pesquise na segunda metade da matriz.
Repita as mesmas etapas até que um elemento seja encontrado ou exaurido na área de pesquisa. Nesse algoritmo, toda vez que a área de pesquisa está reduzindo. Portanto, o número de comparações é no máximo log (N + 1). Como resultado, é um algoritmo eficiente quando comparado à pesquisa linear, mas a matriz deve ser classificada antes de fazer a pesquisa binária.
C Programa para encontrar um elemento com técnica de busca binária.
#include void main () {int eu, imploro, fim, meio, n, procura, matriz [100]; printf ("Digite o número do elemento \ n"); scanf ("% d", & n); printf ("Digite os números% d \ n", n); para (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Digite o número a ser pesquisado \ n"); scanf ("% d" e pesquisa); beg = 0; end = n - 1; meio = (implorar + fim) / 2; while (beg <= end) {if (ordem [meio] fim) printf ("A busca é mal sucedida!% d não está presente na lista. \ n", pesquisa); getch (); } Principais diferenças entre pesquisa linear e pesquisa binária
- A pesquisa linear é de natureza iterativa e usa uma abordagem sequencial. Por outro lado, a pesquisa binária implementa a abordagem de dividir e conquistar.
- A complexidade de tempo da pesquisa linear é O (N), enquanto a pesquisa binária tem O (log 2 N).
- O melhor caso de tempo na pesquisa linear é para o primeiro elemento, ou seja, O (1). Em contraste, na pesquisa binária, é para o elemento do meio, ou seja, O (1).
- Na pesquisa linear, o pior caso para pesquisar um elemento é o número N de comparação. Em contraste, é log 2 N número de comparação para pesquisa binária.
- A pesquisa linear pode ser implementada em uma matriz, bem como na lista vinculada, enquanto a pesquisa binária não pode ser implementada diretamente na lista vinculada.
- Como sabemos, a pesquisa binária exige que o array ordenado seja o motivo. Ele exige que o processamento seja inserido no local adequado para manter uma lista classificada. Pelo contrário, a pesquisa linear não requer elementos classificados, portanto, os elementos são facilmente inseridos no final da lista.
- A pesquisa linear é fácil de usar e não há necessidade de elementos ordenados. Por outro lado, o algoritmo de busca binária é complicado, e os elementos são necessariamente organizados em ordem.
Conclusão
Ambos os algoritmos de pesquisa linear e binária podem ser úteis dependendo da aplicação. Quando uma matriz é a estrutura de dados e os elementos são organizados em ordem de classificação, a pesquisa binária é preferida para pesquisa rápida . Se a lista vinculada for a estrutura de dados, independentemente de como os elementos são organizados, a pesquisa linear é adotada devido à indisponibilidade da implementação direta do algoritmo de pesquisa binária.
O típico algoritmo de pesquisa binária não pode ser empregado na lista vinculada porque a lista vinculada é dinâmica por natureza e não é conhecida onde o elemento do meio é realmente atribuído. Portanto, há um requisito para projetar a variação do algoritmo de busca binária que pode trabalhar na lista vinculada também porque a pesquisa binária é mais rápida na execução do que uma pesquisa linear.
