introduction searching algorithms c
O prezentare generală a căutării algoritmilor în C ++.
Continuăm să căutăm ceva sau altul în viața noastră de zi cu zi. La fel ca viața noastră de zi cu zi, ca profesionist în software, trebuie să căutăm informații pe computerul nostru. Recuperarea informațiilor ar trebui făcută rapid, întrucât nu ne putem permite să pierdem mult din timpul nostru căutând informații.
Prin urmare, avem nevoie de câteva tehnici de căutare eficiente sau algoritmi care pot căuta o anumită informație într-un timp scurt și pot da utilizatorului astfel încât utilizatorul să poată continua cu celelalte sarcini.
=> Vizitați aici pentru lista completă de tutoriale C ++.
Ce veți învăța:
Tehnici de căutare
Avem două tehnici principale de căutare care sunt utilizate în principal pentru a căuta informații.
Acestea includ:
- Căutare liniară
- Căutare binară
În acest tutorial, vom explora în detaliu aceste două tehnici de căutare.
Căutare liniară
Aceasta este cea mai de bază tehnică de căutare și este și mai ușor de implementat. Într-o căutare liniară, cheia care trebuie căutată este comparată liniar cu fiecare element al colectării datelor. Această tehnică funcționează eficient pe structuri de date liniare.
Să luăm în considerare următoarea matrice.
Deasupra este matricea de șapte elemente. Dacă dorim să căutăm cheia = 23, atunci începând de la 0aelement, valoarea cheie va fi comparată cu fiecare element. Odată ce elementul cheie se potrivește cu elementul din matrice, atunci locația respectivă va fi returnată. În acest caz locația, 4 va fi returnată, deoarece valoarea cheie se potrivește cu valoarea din locația respectivă.
Am implementat o căutare liniară folosind limbajul C ++ și Java de mai jos.
Implementare 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 '< Ieșire:
site-uri pentru a descărca videoclipuri de pe YouTube
Matricea de intrare este
21 43 23 54 75 13 5 8 25 10
Introduceți cheia de căutat: 3
Nu s-a putut găsi cheia dată în matrice
Matricea de intrare este
21 43 23 54 75 13 5 8 25 10
Introduceți cheia de căutat: 75
Cheie găsită în poziția 5 din matrice
Implementare 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'); } }
Ieșire:
Matricea de intrare este
21 43 23 54 75 13 5 8 25 10
Introduce cheia
2. 3
cheie găsită la locația 3
Căutarea liniară poate fi efectuată pe orice structură de date liniară cu elemente sortate sau nesortate. Dar durează mai mult dacă există prea multe elemente și dacă elementul cheie este spre final, deoarece fiecare element este comparat cu valoarea cheie.
Căutare binară
Căutarea binară este o tehnică care folosește tehnica „împarte și cucerește” pentru a căuta o cheie. Funcționează pe o listă liniară sortată de elemente. Lista sortată este cerința de bază pentru ca o căutare binară să funcționeze.
În metoda de căutare binară, lista este împărțită în mod repetat în jumătate și elementul cheie este căutat în ambele jumătăți ale listei până când cheia este găsită.
De exemplu,să luăm următoarea matrice sortată de 10 elemente.

Să spunem că cheia = 21 trebuie căutată în matrice.
Să calculăm locația de mijloc a matricei.
Mijloc = 0 + 9/2 = 4
asigurarea calității software-ului în ingineria software-ului
De exemplu,să luăm următoarea matrice sortată de 10 elemente.

Cheie = 21
În primul rând, vom compara valoarea cheie cu elementul (mid). Constatăm că valoarea elementului la mijlocul = 21.

Astfel găsim acea cheie = (mijloc). Prin urmare, cheia este găsită.
cheie = 25

Mai întâi comparăm valoarea cheie cu mijlocul. Deci (21<25), we will directly search for the key in the upper half of the array.

Acum, din nou, vom găsi mijlocul pentru jumătatea superioară a matricei.
Mijloc = 4 + 9/2 = 6
Valoarea la locație (mijloc) = 25

care nu este unul dintre tipurile de articole testate în timpul testării sistemului?
Acum comparăm elementul cheie cu elementul mijlociu. Deci (25 == 25), astfel am găsit cheia la locația (mijloc).
Împărțim în mod repetat matricea și comparând elementul cheie cu mijlocul, decidem în ce jumătate să căutăm cheia.
Mai jos sunt prezentate implementarea C ++ și Java pentru căutare binară.
Implementare 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 '< Ieșire:
Matricea de intrare este
5 8 10 13 21 23 25 43 54 75
Introduceți cheia care trebuie căutată: 21
Cheie găsită la locația 5

Implementare 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) Ieșire:
Matricea de intrare este
5 8 10 13 21 23 25 43 54 75
Introduceți cheia de căutat
douăzeci și unu
locația cheii este 5
Căutarea binară este mai eficientă în ceea ce privește timpul și corectitudinea. Tehnica de căutare liniară este utilizată rar, deoarece este mai greoaie și mai lentă. Căutarea binară este mult mai rapidă în comparație cu o căutare liniară.
Concluzie
Tehnicile de căutare ne ajută să căutăm informații stocate pe un computer, astfel încât utilizatorul să poată continua cu celelalte sarcini de prelucrare a informațiilor. Tehnica de căutare liniară este simplă și mai ușoară, dar nu este utilizată pe scară largă.
Tehnica de căutare binară este mult mai rapidă și eficientă, prin urmare este utilizată pe scară largă.
În viitorul nostru tutorial, vom explora în detaliu diferitele tehnici de sortare.
=> Consultați aici ghidul perfect de formare C ++.
Lectură recomandată
- Introducere în limbajul de programare Java - Video Tutorial
- Introducere în Appium Studio: Avantaje și caracteristici cheie
- Algoritmi în STL
- Cea mai bună serie de tutoriale GRATUITE C #: Ghidul final C # pentru începători
- JMeter Video 1: Introducere, descărcare și instalare JMeter
- Introducere și proces de instalare Python
- Ce este Unix: o scurtă introducere în Unix
- Introducere în Micro Focus LoadRunner - Testarea încărcării cu LoadRunner Tutorial # 1