introduction searching algorithms c
Una visió general de la cerca d'algorismes en C ++.
Seguim buscant alguna cosa o altra a la nostra vida quotidiana. Igual que la nostra vida quotidiana, com a professional del programari, hem de buscar informació al nostre ordinador. La recuperació d’informació s’hauria de fer ràpidament, ja que no ens podem permetre perdre gran part del nostre temps buscant informació.
Per tant, necessitem algunes tècniques o algorismes de cerca eficients que puguin cercar una informació determinada en poc temps i donar-la a l'usuari perquè l'usuari pugui continuar amb les altres tasques.
=> Visiteu aquí la llista completa de tutorials de C ++.
Què aprendreu:
Tècniques de cerca
Disposem de dues tècniques de cerca principals que s’utilitzen principalment per cercar informació.
Això inclou:
- Cerca lineal
- Cerca binària
En aquest tutorial, explorarem amb detall aquestes dues tècniques de cerca.
Cerca lineal
Aquesta és la tècnica de cerca més bàsica i també és més fàcil d’implementar. En una cerca lineal, la clau a cercar es compara linealment amb tots els elements de la recopilació de dades. Aquesta tècnica funciona eficaçment en estructures de dades lineals.
Considerem la següent matriu.
A la part superior es mostra la matriu de set elements. Si volem cercar la clau = 23, a partir del 0thelement, el valor clau es compararà amb cada element. Un cop l'element clau coincideixi amb l'element de la matriu, es retornarà aquesta ubicació concreta. En aquest cas, es retornarà 4, ja que el valor-clau coincideix amb el valor d’aquesta ubicació.
A continuació, hem implementat una cerca lineal mitjançant llenguatge C ++ i Java.
Implementació de 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 '< Sortida:
obriu un fitxer apk a Windows
La matriu d’entrada és
21 43 23 54 75 13 5 8 25 oct
Introduïu la clau que voleu cercar: 3
No s'ha pogut trobar la clau donada a la matriu
La matriu d’entrada és
21 43 23 54 75 13 5 8 25 oct
Introduïu la clau a cercar: 75
La clau es troba a la posició 5 de la matriu
Implementació de 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'); } } Sortida:
La matriu d’entrada és
21 43 23 54 75 13 5 8 25 oct
Tecla d'introducció
23
clau trobada a la ubicació 3
La cerca lineal es pot realitzar en qualsevol estructura de dades lineal que tingui elements ordenats o no classificats. Però triga més temps si hi ha massa elements i si l'element clau es troba cap al final, ja que cada element es compara amb el valor clau.
Cerca binària
La cerca binària és una tècnica que utilitza la tècnica de 'dividir i conquerir' per cercar una clau. Funciona en una llista lineal ordenada d'elements. La llista ordenada és el requisit bàsic perquè funcioni una cerca binària.
En el mètode de cerca binària, la llista es divideix repetidament en meitats i es busca l'element clau a les dues meitats de la llista fins que es troba la clau.
Per exemple,agafem la següent matriu ordenada de 10 elements.
Diguem que la clau = 21 s'ha de cercar a la matriu.
Calculem la ubicació mitjana de la matriu.
Mitjà = 0 + 9/2 = 4
Per exemple,agafem la següent matriu ordenada de 10 elements.
Clau = 21
En primer lloc, compararem el valor clau amb l'element (mid). Trobem que el valor de l’element a mitjan = 21.
com executar el fitxer jar a Windows 10
Així trobem aquesta clau = (mid). Per tant, es troba la clau.
clau = 25
Primer comparem el valor clau amb la mitjana. Així doncs (21<25), we will directly search for the key in the upper half of the array.
Ara de nou trobarem la meitat de la meitat superior de la matriu.
Mitjà = 4 + 9/2 = 6
El valor a la ubicació (mitjan) = 25
Ara comparem l’element clau amb l’element mitjà. Per tant (25 == 25), hem trobat la clau a la ubicació (mitja).
Dividim repetidament la matriu i, comparant l’element clau amb el mitjà, decidim en quina meitat cercarem la clau.
A continuació es detallen la implementació C ++ i Java per a la cerca binària.
Implementació de 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 '< Sortida:
La matriu d’entrada és
5 8 10 13 21 23 25 43 54 75
Introduïu la clau que voleu cercar: 21
Clau trobada a la ubicació 5
Implementació de 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) Sortida:
La matriu d’entrada és
5 8 10 13 21 23 25 43 54 75
Introduïu la clau que voleu cercar
21
la ubicació de la clau és 5
La cerca binària és més eficient quant a temps i correcció. La tècnica de cerca lineal poques vegades s’utilitza, ja que és més feixuga i més lenta. La cerca binària és molt més ràpida en comparació amb una cerca lineal.
eines de proves d'api de codi obert
Conclusió
Les tècniques de cerca ens ajuden a buscar informació emmagatzemada en un ordinador perquè l'usuari pugui continuar amb les altres tasques de processament de la informació. La tècnica de cerca lineal és senzilla i senzilla, però no s’utilitza àmpliament.
La tècnica de cerca binària és molt més ràpida i eficient, per tant s’utilitza àmpliament.
Al nostre proper tutorial, explorarem detalladament les diverses tècniques d’ordenació.
=> Consulteu aquí la guia de formació perfecta de C ++.
Lectura recomanada
- Introducció al llenguatge de programació Java: vídeo tutorial
- Introducció a Appium Studio: avantatges i funcions clau
- Algorismes a STL
- Millor sèrie de tutorials C # GRATU :TS: la millor guia C # per a principiants
- Vídeo JMeter 1: Introducció, descàrrega i instal·lació de JMeter
- Introducció i procés d’instal·lació de Python
- Què és Unix: una breu introducció a Unix
- Introducció a Micro Focus LoadRunner: proves de càrrega amb LoadRunner Tutorial # 1
