Contente

• Gráfico de comparação
• Definição de Pesquisa Linear
• Definição de Pesquisa Binária
• Conclusão

Pesquisa linear e pesquisa binária são os dois métodos usados ​​em matrizes para procurando os elementos. A pesquisa é um processo de localização de um elemento na lista de elementos armazenados em qualquer ordem ou aleatoriamente.

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. Portanto, 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 ordenado enquanto na pesquisa linear não existe esse pré-requisito. Embora ambos os métodos de pesquisa usem técnicas diferentes, discutidas abaixo.

1. Gráfico de comparação
2. Definição
3. Principais diferenças
4. Conclusão

Gráfico de comparação

Base para comparação	Pesquisa linear	Pesquisa binária
Complexidade temporal	EM)	O (log 2 N)
Melhor caso	Primeiro elemento O (1)	Elemento central O (1)
Pré-requisito para uma matriz	Não exigido	A matriz deve estar na ordem classificada
Pior caso para N número de elementos	N comparações são necessárias	Pode concluir após apenas o log2Comparações de N
Pode ser implementado em	Matriz e lista vinculada	Não pode ser implementado diretamente na lista vinculada
Inserir operação	Facilmente inserido no final da lista	Exija que o processamento seja inserido no local apropriado para manter uma lista classificada.
Tipo de algoritmo	Iterativo por natureza	Divida e conquiste na natureza
Utilidade	Fácil de usar e sem a necessidade de quaisquer elementos solicitados.	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 por um em uma ordem lógica e verificado se é o elemento desejado ou não. Uma pesquisa não terá êxito se todos os elementos forem acessados ​​e o elemento desejado não for encontrado. Na pior das hipóteses, o número médio de casos em que talvez tenhamos que digitalizar metade do tamanho da matriz (n / 2).

Portanto, a pesquisa linear pode ser definida como a técnica que percorre a matriz seqüencialmente para localizar o item especificado. O programa abaixo ilustra a pesquisa de um elemento da matriz usando a pesquisa.

Eficiência de pesquisa 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, apenas uma comparação será feita. Quando o registro desejado é o último, n comparações devem ser feitas. Se o registro for apresentado em algum lugar da tabela de pesquisa, em média, o número de comparações será (n + 1/2). A pior eficiência dessa técnica é O (n), que significa a ordem de execução.

Programa C para pesquisar um elemento com a técnica de pesquisa linear.

#incluir #incluir void main () {int a, n, i, item, loc = -1; clrscr (); f (" nInsira o número do elemento:"); scanf ("% d", & n); f ("Digite os números: n"); para (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nInsira o número a ser pesquisado:"); scanf ("% d", & item); para (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; pausa; }} if (loc> = 0) {f (" n% d é encontrado na posição% d:", item, loc + 1); } else {f (" n O item não existe"); } getch (); }

Definição de Pesquisa Binária

A pesquisa binária é um algoritmo extremamente eficiente. Essa técnica de pesquisa consome menos tempo na pesquisa do item fornecido nas comparações mínimas possíveis. Para fazer a pesquisa binária, primeiro, temos que classificar os elementos da matriz.

A lógica por trás dessa técnica é apresentada abaixo:

• Primeiro, encontre o elemento do meio da matriz.
• O elemento do meio da matriz é comparado ao elemento a ser pesquisado.

Existem três casos podem surgir:

1. Se o elemento for o elemento necessário, a pesquisa será bem-sucedida.
2. Quando o elemento for menor que o item desejado, pesquise apenas a primeira metade da matriz.
3. Se for maior que o elemento desejado, pesquise na segunda metade da matriz.

Repita as mesmas etapas até que um elemento seja encontrado ou se esgote na área de pesquisa. Nesse algoritmo, toda vez que a área de pesquisa está diminuindo. 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 precisa ser classificada antes de fazer a pesquisa binária.

Programa C para encontrar um elemento com a técnica de pesquisa binária.

#incluir void main () {int i, beg, end, middle, n, pesquisa, array; f ("Digite o número do elemento n"); scanf ("% d", & n); f ("Digite os% d números n", n); para (i = 0; i <n; i ++) scanf ("% d", & array); f ("Digite o número a ser pesquisado n"); scanf ("% d", & pesquisa); beg = 0; fim = n - 1; meio = (início + fim) / 2; while (beg <= end) {if (array <pesquisa) beg = middle + 1; caso contrário, se (matriz == pesquisa) {f ("A pesquisa foi bem-sucedida. n% d encontrada no local% d. n", pesquisa, meio + 1); pausa; } else fim = meio - 1; meio = (início + fim) / 2; } if (beg> end) f ("A pesquisa não teve êxito!% d não está presente na lista. n", pesquisa); getch (); }

1. A pesquisa linear é de natureza iterativa e usa abordagem seqüencial. Por outro lado, a pesquisa binária implementa a abordagem de dividir e conquistar.
2. A complexidade temporal da pesquisa linear é O (N), enquanto a pesquisa binária possui O (log₂N)
3. O melhor caso na pesquisa linear é para o primeiro elemento, ou seja, O (1). Por outro lado, na pesquisa binária, é para o elemento do meio, ou seja, O (1).
4. Na pesquisa linear, o pior caso para pesquisar um elemento é o número N de comparação. Por outro lado, é log₂N número de comparação para pesquisa binária.
5. A pesquisa linear pode ser implementada em uma matriz e na lista vinculada, enquanto a pesquisa binária não pode ser implementada diretamente na lista vinculada.
6. Como sabemos, a pesquisa binária exige que a matriz classificada seja o motivo. É necessário que o processamento seja inserido no local apropriado 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.
7. A pesquisa linear é fácil de usar e não é necessário nenhum elemento ordenado. Por outro lado, o algoritmo de busca binária é complicado, e os elementos são necessariamente organizados em ordem.

Conclusão

Os algoritmos de pesquisa linear e binário podem ser úteis, dependendo da aplicação. Quando uma matriz é a estrutura de dados e os elementos são organizados em ordem classificada, a pesquisa binária é preferida para rápidoprocurando. Se a lista vinculada for a estrutura de dados, independentemente da organização dos elementos, a pesquisa linear será adotada devido à indisponibilidade da implementação direta do algoritmo de pesquisa binária.

O algoritmo típico de pesquisa binária não pode ser empregado na lista vinculada porque a lista vinculada é de natureza dinâmica e não se sabe onde o elemento do meio está realmente atribuído. Portanto, existe um requisito para projetar a variação do algoritmo de pesquisa binária que também pode funcionar na lista vinculada, porque a pesquisa binária é mais rápida na execução do que uma pesquisa linear.