introduction searching algorithms c
Uma Visão Geral dos Algoritmos de Pesquisa em C ++.
Continuamos procurando por uma coisa ou outra em nossa vida cotidiana. Assim como em nosso dia a dia, como profissionais de software, precisamos buscar informações em nosso computador. A recuperação de informações deve ser feita rapidamente, pois não podemos perder muito do nosso tempo procurando informações.
Portanto, precisamos de algumas técnicas ou algoritmos de busca eficientes que possam buscar uma determinada informação em um curto espaço de tempo e dar ao usuário para que ele possa prosseguir com as outras tarefas.
=> Visite aqui para obter a lista completa de tutoriais em C ++.
O que você aprenderá:
Técnicas de Pesquisa
Temos duas técnicas de pesquisa principais que são utilizadas principalmente para pesquisar informações.
Esses incluem:
- Pesquisa Linear
- Pesquisa Binária
Neste tutorial, exploraremos essas duas técnicas de pesquisa em detalhes.
Pesquisa Linear
Esta é a técnica de pesquisa mais básica e mais fácil de implementar. Em uma pesquisa linear, a chave a ser pesquisada é comparada linearmente com cada elemento da coleta de dados. Essa técnica funciona de forma eficaz em estruturas de dados lineares.
Vamos considerar a seguinte matriz.
Acima está a matriz de sete elementos. Se quisermos pesquisar a chave = 23, a partir de 0ºelemento, o valor da chave será comparado a cada elemento. Assim que o elemento-chave corresponder ao elemento na matriz, esse local específico será retornado. Nesse caso, local, 4 será retornado, pois o valor-chave corresponde ao valor naquele local.
Implementamos uma pesquisa linear usando a linguagem C ++ e Java abaixo.
Implementação C ++
#include #include using namespace std; int main() { int myarray[10] = {21,43,23,54,75,13,5,8,25,10}; int key,loc; cout<<'The input array is'<key; for (int i = 0; i<10; i++) { if(myarray[i] == key) { loc = i+1; break; } else loc = 0; } if(loc != 0) { cout<<'Key found at position '< Resultado:
perguntas e respostas da entrevista de design de banco de dados
A matriz de entrada é
21 43 23 54 75 13 5 8 25 10
Digite a chave a ser pesquisada: 3
Não foi possível encontrar a chave fornecida na matriz
A matriz de entrada é
21 43 23 54 75 13 5 8 25 10
Digite a chave a ser pesquisada: 75
Chave encontrada na posição 5 na matriz
Implementação Java
import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main(String[] args) { int[] myarray = {21,43,23,54,75,13,5,8,25,10}; int key,location=0; Scanner sc = new Scanner(System.in); System.out.println('The input array is'); for(int i=0;i<10;i++){ System.out.print(myarray[i]+' '); } System.out.println('
'); System.out.println('Enter key'); key = sc.nextInt(); for(int i = 0; i<10; i++) { if(myarray[i]==key) { location = i+1; break; } else location = 0; } if(location != 0) { System.out.println('key found at location ' + location); } else System.out.println('Key not found'); } }
Resultado:
A matriz de entrada é
21 43 23 54 75 13 5 8 25 10
o que você pode fazer com c ++
Tecla Enter
2,3
chave encontrada na localização 3
A pesquisa linear pode ser realizada em qualquer estrutura de dados linear com elementos classificados ou não classificados. Mas leva mais tempo se houver muitos elementos e se o elemento-chave estiver próximo ao final, pois cada elemento é comparado com o valor-chave.
Pesquisa Binária
A pesquisa binária é uma técnica que usa a técnica de “dividir para conquistar” para pesquisar uma chave. Funciona em uma lista linear classificada de elementos. A lista classificada é o requisito básico para que uma pesquisa binária funcione.
No método de pesquisa binária, a lista é repetidamente dividida ao meio e o elemento-chave é pesquisado em ambas as metades da lista até que a chave seja encontrada.
Por exemplo,vamos pegar a seguinte matriz classificada de 10 elementos.
Digamos que a chave = 21 deve ser pesquisada na matriz.
Vamos calcular a localização do meio do array.
Médio = 0 + 9/2 = 4
Por exemplo,vamos pegar a seguinte matriz classificada de 10 elementos.
Chave = 21
Primeiro, compararemos o valor-chave com o elemento [mid]. Descobrimos que o valor do elemento em mid = 21.
Assim, encontramos essa chave = [mid]. Portanto, a chave foi encontrada.
chave = 25
Primeiro, comparamos o valor-chave com o meio. Então (21<25), we will directly search for the key in the upper half of the array.
Agora, novamente, encontraremos o meio para a metade superior da matriz.
Médio = 4 + 9/2 = 6
O valor no local [mid] = 25
Agora comparamos o elemento-chave com o elemento médio. Portanto (25 == 25), encontramos a chave no local [mid].
Repetidamente dividimos a matriz e, comparando o elemento-chave com o meio, decidimos em qual metade procurar a chave.
A seguir, são fornecidas as implementações C ++ e Java para pesquisa binária.
Implementação C ++
#include #include using namespace std; int binarySearch(int myarray[], int beg, int end, int key) { int mid; if(end >= beg) { mid = (beg + end)/2; if(myarray[mid] == key) { return mid+1; } else if(myarray[mid] key; location = binarySearch(myarray, 0, 9, key); if(location != -1) { cout<<'Key found at location '< Resultado:
A matriz de entrada é
5 8 10 13 21 23 25 43 54 75
Digite a chave que deve ser pesquisada: 21
Chave encontrada no local 5
Implementação Java
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main(String[] args) { int[] myarray = {5,8,10,13,21,23,25,43,54,75}; int key, location = -1; System.out.println('The input array is'); for(int i=0;i= beg) { mid = (beg + end)/2; if(myarray[mid] == key) { return mid+1; } else if(myarray[mid] Resultado:
A matriz de entrada é
5 8 10 13 21 23 25 43 54 75
Digite a chave a ser pesquisada
vinte e um
a localização da chave é 5
A pesquisa binária é mais eficiente em termos de tempo e correção. A técnica de pesquisa linear raramente é usada, pois é mais complicada e mais lenta. A pesquisa binária é muito mais rápida quando comparada a uma pesquisa linear.
Conclusão
As técnicas de busca nos ajudam a buscar informações armazenadas em um computador para que o usuário possa prosseguir com as outras tarefas de processamento de informações. A técnica de pesquisa linear é simples e fácil, mas não é usada extensivamente.
A técnica de pesquisa binária é muito mais rápida e eficiente, portanto, é amplamente utilizada.
declara um array de string em java
Em nosso próximo tutorial, exploraremos as várias técnicas de classificação em detalhes.
=> Confira o guia de treinamento perfeito C ++ aqui.
Leitura recomendada
- Introdução à linguagem de programação Java - tutorial em vídeo
- Introdução ao Appium Studio: Principais benefícios e recursos
- Algoritmos em STL
- Best FREE C # Tutorial Series: The Ultimate C # Guide for Beginners
- Vídeo 1 do JMeter: introdução, download do JMeter e instalação
- Introdução ao Python e processo de instalação
- O que é Unix: uma breve introdução ao Unix
- Introdução ao Micro Focus LoadRunner - Teste de carga com LoadRunner Tutorial # 1