Мени

Увод у претраживање алгоритама на језику Ц ++

introduction searching algorithms c

Испробајте Наш Инструмент За Елиминисање Проблема

Преглед претраживања алгоритама на језику Ц ++.

Стално тражимо нешто или друго у свакодневном животу. Баш као и у нашем свакодневном животу, и ми као софтверски професионалац морамо тражити информације на рачунару. До проналажења информација треба доћи брзо, јер не можемо себи приуштити да губимо већи део свог времена у потрази за информацијама.

Отуда су нам потребне неке ефикасне технике претраживања или алгоритми који могу да претраже одређени податак у кратком времену и дају га кориснику како би корисник могао да настави са осталим задацима.

=> Посетите овде за комплетну листу водича за Ц ++.

ПРЕТРАЖИВАЊЕ АЛГОРИТМА У Ц ++

Шта ћете научити:

Технике претраживања

Имамо две главне технике претраживања које се углавном користе за тражење информација.

Ови укључују:

  • Линеарна претрага
  • Бинарна претрага

У овом упутству детаљно ћемо истражити обе ове технике претраживања.

Линеарна претрага

Ово је најосновнија техника претраживања и лакша је за примену. У линеарном претраживању, кључ који се претражује упоређује се линеарно са свим елементима збирке података. Ова техника ефикасно делује на линеарним структурама података.

Размотримо следећи низ.

Низ линеарне претраге

Изнад је низ од седам елемената. Ако желимо да претражимо кључ = 23, онда почев од 0тхелемент, кључна вредност ће се упоређивати са сваким елементом. Једном када се кључни елемент подудара са елементом у низу, тада ће се вратити та одређена локација. У овом случају локација 4 ће се вратити јер се кључ / вредност подудара са вредношћу на тој локацији.

Спровели смо линеарно претраживање користећи Ц ++ и Јава језик у наставку.

Имплементација Ц ++

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

Излаз:

виртуелни уређај за уравнотежење оптерећења отвореног кода

Улазни низ је
21 43 23 54 75 13 5 8 25 10
Унесите кључ за претрагу: 3
Није могуће пронаћи дати кључ у низу

Улазни низ је
21 43 23 54 75 13 5 8 25 10
Унесите кључ за претрагу: 75
Кључ се налази на положају 5 у низу

Имплементација Јаве

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

Излаз:

Улазни низ је

21 43 23 54 75 13 5 8 25 10

Типка на тастатури

2. 3

кључ пронађен на локацији 3

Линеарно претраживање може се извршити на било којој линеарној структури података која има сортиране или несортиране елементе. Али треба више времена ако има превише елемената и ако је кључни елемент при крају, јер се сваки елемент упоређује са кључном вредношћу.

Бинарна претрага

Бинарна претрага је техника која користи технику „подели и освоји“ за тражење кључа. Ради на разврстаној линеарној листи елемената. Сортирана листа је основни услов за функционисање бинарне претраге.

У бинарном начину претраживања, листа је више пута подељена на пола и кључни елемент се претражује у обе половине листе док се кључ не пронађе.

На пример,узмимо следећи сортирани низ од 10 елемената.

Бинарна претрага

Рецимо да се кључ = 21 тражи у низу.

Израчунајмо средину локације низа.

Средина = 0 + 9/2 = 4

На пример,узмимо следећи сортирани низ од 10 елемената.

имплементација двоструко повезане листе у јави

израчунати средњу локацију

Кључ = 21

Прво ћемо упоредити кључну вредност са елементом (мид). Откривамо да је вредност елемента у средини = 21.

упоредите кључну вредност са елементом (мид)

Тако налазимо да је кључ = (мид). Отуда је кључ пронађен.

кључ = 25

кључ = (средина)

Прво упоређујемо кључну вредност са средином. Дакле (21<25), we will directly search for the key in the upper half of the array.

упоредите кључну вредност са средином

Сада ћемо поново наћи средину за горњу половину низа.

Средина = 4 + 9/2 = 6

Вредност на локацији (мид) = 25

Вредност на локацији (мид) = 25

Сада упоређујемо кључни елемент са средњим елементом. Дакле (25 == 25), па смо пронашли кључ на локацији (средина).

Више пута поделимо низ и упоређујући кључни елемент са средином, одлучујемо у којој половини ћемо тражити кључ.

Доље су дати имплементација Ц ++ и Јава за бинарно претраживање.

Имплементација Ц ++

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

Излаз:

Улазни низ је
5 8 10 13 21 23 25 43 54 75
Унесите кључ који треба претражити: 21
Кључ пронађен на локацији 5

Бинарна претрага ц ++

Имплементација Јаве

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)

Излаз:

Улазни низ је

5 8 10 13 21 23 25 43 54 75

Унесите кључ за претрагу

двадесет један

место кључа је 5

како пријавити ред у јави

Бинарна претрага је ефикаснија у погледу времена и исправности. Техника линеарног претраживања ретко се користи јер је гломазнија и спорија. Бинарна претрага је много бржа у поређењу са линеарном претрагом.

Закључак

Технике претраживања помажу нам да тражимо информације ускладиштене на рачунару како би корисник могао да настави са осталим задацима обраде информација. Техника линеарног претраживања је једноставна и лакша, али се не користи широко.

Бинарна техника претраживања је много бржа и ефикаснија, па се стога широко користи.

У нашем предстојећем упутству детаљно ћемо истражити разне технике сортирања.

=> Овде погледајте савршен водич за обуку за Ц ++.

Препоручено читање

^