Meni

Uvod v iskanje algoritmov v jeziku C ++

introduction searching algorithms c

Pregled iskanja algoritmov v jeziku C ++.

V vsakdanjem življenju nenehno iščemo nekaj ali drugega. Tako kot v vsakdanjem življenju moramo tudi mi kot strokovnjak za programsko opremo informacije iskati v svojem računalniku. Iskanje informacij je treba opraviti hitro, saj si ne moremo privoščiti, da bi veliko časa izgubljali z iskanjem informacij.

Zato potrebujemo nekaj učinkovitih iskalnih tehnik ali algoritmov, ki lahko v kratkem času poiščejo določeno informacijo in jo dajo uporabniku, da lahko uporabnik nadaljuje z drugimi nalogami.

=> Obiščite tukaj za celoten seznam vadnic za C ++.

ISKANJE ALGORITMOV V C ++

Kaj se boste naučili:

Iskalne tehnike

Imamo dve glavni tehniki iskanja, ki sta večinoma uporabljeni za iskanje informacij.

Tej vključujejo:

  • Linearno iskanje
  • Binarno iskanje

V tej vadnici bomo podrobno preučili obe teh iskalnih tehnik.

Linearno iskanje

To je najosnovnejša tehnika iskanja, ki jo je tudi lažje izvajati. Pri linearnem iskanju se ključ, ki ga iščete, linearno primerja z vsakim elementom zbirke podatkov. Ta tehnika učinkovito deluje na linearnih podatkovnih strukturah.

Upoštevajmo naslednjo matriko.

Matrika linearnega iskanja

Zgoraj je niz sedmih elementov. Če želimo iskati ključ = 23, potem začenši z 0thelement, bo vrednost ključa primerjana z vsakim elementom. Ko se ključni element ujema z elementom v matriki, bo vrnjeno to določeno mesto. V tem primeru se vrne lokacija 4, saj se ključ-vrednost ujema z vrednostjo na tej lokaciji.

Spodaj smo izvedli linearno iskanje z uporabo jezika C ++ in Java.

Izvedba 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 '<

Izhod:

Vhodno polje je
21 43 23 54 75 13 5 8 25 10
Vnesite ključ za iskanje: 3
Danega ključa v matriki ni bilo mogoče najti

kateri je najboljši brezplačen čistilec registra

Vhodno polje je
21 43 23 54 75 13 5 8 25 10
Vnesite ključ za iskanje: 75
Ključ najdemo na položaju 5 v matriki

Izvajanje 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'); } }

Izhod:

Vhodno polje je

21 43 23 54 75 13 5 8 25 10

Tipka Enter

2. 3

ključ najden na lokaciji 3

Linearno iskanje je mogoče izvesti v kateri koli linearni podatkovni strukturi z razvrščenimi ali nesortiranimi elementi. Vendar traja dlje časa, če je elementov preveč in če je ključni element proti koncu, saj se vsak element primerja s ključno vrednostjo.

kako si ogledati datoteke eps v oknih

Binarno iskanje

Binarno iskanje je tehnika, ki za iskanje ključa uporablja tehniko »deli in osvoji«. Deluje na razvrščenem linearnem seznamu elementov. Razvrščeni seznam je osnovna zahteva za delovanje binarnega iskanja.

Pri metodi binarnega iskanja se seznam večkrat razdeli na polovico in ključni element išče v obeh polovicah seznama, dokler ključa ne najde.

Na primer,vzemimo naslednjo razvrščeno matriko 10 elementov.

Binarno iskanje

Recimo, da je treba v matriki iskati ključ = 21.

Izračunajmo srednjo lokacijo matrike.

Sredina = 0 + 9/2 = 4

Na primer,vzemimo naslednjo razvrščeno matriko 10 elementov.

izračuna srednjo lokacijo

Ključ = 21

Najprej bomo primerjali ključno vrednost z elementom [mid]. Ugotovili smo, da je vrednost elementa pri sredini = 21.

primerjaj vrednost ključa z elementom [mid]

Tako najdemo, da je ključ = [mid]. Zato je ključ najden.

ključ = 25

tipka = [sredina]

Najprej primerjamo ključno vrednost s srednjo vrednostjo. Torej (21<25), we will directly search for the key in the upper half of the array.

primerjaj ključno vrednost s sredino

kako kopirati matriko java -

Zdaj bomo spet našli sredino za zgornjo polovico polja.

Sredina = 4 + 9/2 = 6

Vrednost na lokaciji [mid] = 25

Vrednost na lokaciji [mid] = 25

Zdaj primerjamo ključni element s srednjim elementom. Torej (25 == 25), zato smo našli ključ na lokaciji [sredi].

Polje večkrat razdelimo in s primerjavo ključnega elementa s sredino odločimo, v kateri polovici bomo iskali ključ.

Spodaj so predstavljeni C ++ in Java za binarno iskanje.

Izvedba 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 '<

Izhod:

Vhodno polje je
5 8 10 13 21 23 25 43 54 75
Vnesite ključ, ki ga želite iskati: 21
Ključ najden na lokaciji 5

Binarno iskanje c ++

Izvajanje 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]

Izhod:

Vhodno polje je

5 8 10 13 21 23 25 43 54 75

Vnesite ključ, ki ga želite iskati

enaindvajset

lokacija ključa je 5

Binarno iskanje je časovno in korektno bolj učinkovito. Tehnika linearnega iskanja se redko uporablja, saj je bolj okorna in počasnejša. Binarno iskanje je veliko hitrejše v primerjavi z linearnim iskanjem.

Zaključek

Tehnike iskanja nam pomagajo iskati informacije, shranjene v računalniku, tako da lahko uporabnik nadaljuje z drugimi nalogami obdelave informacij. Tehnika linearnega iskanja je preprosta in enostavna, vendar se ne uporablja široko.

Tehnika binarnega iskanja je veliko hitrejša in učinkovitejša, zato se pogosto uporablja.

V naši prihajajoči vadnici bomo podrobno raziskali različne tehnike razvrščanja.

=> Tukaj si oglejte Perfect Guide za usposabljanje za C ++.

Priporočeno branje

^