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

Итеративни метод има просторну сложеност од О(1) у односу на О(пријава) произведен рекурзивним методом. Дакле, како можете имплементирати алгоритам бинарног претраживања користећи итеративни метод у Ц, Ц++ и Питхон-у?

Шта је бинарно претраживање?

Бинарна претрага позната и као претрага у пола интервала, логаритамска претрага или бинарно пресецање је алгоритам који претражује и враћа позицију елемента у сортираном низу. Елемент за претрагу се упоређује са средњим елементом. Узимајући просек доње и горње границе, можете пронаћи средње елементе.

Ако је елемент за претрагу већи од средњег елемента, то значи да су сви елементи на левој страни мањи од елемента за претрагу. Дакле, контрола се помера на десну страну низа (ако је низ у растућем редоследу) повећањем доње границе на следећу позицију средњег елемента.

instagram viewer

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

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

Ево дијаграмског приказа Алгоритам бинарног претраживања:

Бинарно претраживање помоћу Ц

Пратите ове кораке да бисте применили бинарну претрагу користећи Ц:

Цео изворни код програма за бинарну претрагу који користи Ц, Ц++, Јава и Питхон је присутан у овом ГитХуб спремиште.

Програм дефинише функцију, бинариСеарцх(), који враћа или индекс пронађене вредности или -1 ако није присутан:

#инцлуде <стдио.х>
интбинариСеарцх(инт арр[], инт арр_сизе, инт претрага_број){
/*... */
}

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

Тхе ниско и висока променљиве чувају индексе који представљају границе тренутног простора за претрагу. мид складишти индекс у средини:

инт лов = 0, високо = арр_сизе - 1, мид;

Главни док() петља ће сузити простор за претрагу. Ако вредност ниског индекса икада постане већа од високог индекса, онда је простор за претрагу исцрпљен, тако да вредност не може бити присутна.

док (ниска <= висока) {
/* наставља... [1] */
 }
повратак-1;

Након ажурирања средње тачке на почетку петље, постоје три могућа исхода:

  1. Ако је вредност на средини она коју тражимо, вратите тај индекс.
  2. Ако је средња вредност већа од оне коју тражимо, смањите највишу.
  3. Ако је средња вредност мања, повећајте најнижу. 
/* [1] ...наставак */
 средња = (ниска + (висока - ниска)) / 2;
иф (арр[мид] == број_претраживања)
повратак мид;
другоако (арр[мид] > сеарцх_нумбер)
 висока = средња - 1;
друго
 низак = средњи + 1;

Тестирајте функцију са корисничким уносом. Користите сцанф() да добијете унос из командне линије, укључујући величину низа, његов садржај и број за претрагу:

интглавни(){
инт арр[100], и, арр_сизе, сеарцх_нумбер;
 принтф("Унесите број елемената: ");
 сцанф("%д", &арр_сизе);
 принтф("Унесите бројеве: ");
за (и = 0; и < арр_сизе; и++) {
 сцанф("%д", &арр[и]);
 }


принтф("Унесите број за претрагу: ");
 сцанф("%д", &сеарцх_нумбер);


и = бинариСеарцх (арр, арр_сизе, сеарцх_нумбер);


ако (и==-1)
 принтф("Број није присутан");
друго
 принтф("Број је присутан на позицији %д", и + 1);
повратак0;
}

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

Бинарно претраживање користећи Ц++

Можете конвертовати Ц програм у Ц++ програм увозом Инпут Оутпут Стреам и користите именски простор стд како би се избегло понављање више пута током програма.

#инцлуде <иостреам>
Користећи именског просторастд;

Користите цоут са оператором екстракције << уместо принтф() и цин са оператором уметања >> уместо сцанф() и ваш Ц++ програм је спреман.

принтф("Унесите број елемената: ");
цоут <<"Унесите број елемената: ";
сцанф("%д", &арр_сизе);
цин >> арр_сизе;

Бинарно претраживање користећи Питхон

Пошто Питхон нема уграђену подршку за низове, користите листе. Дефинишите функцију, бинариСеарцх(), који прихвата три параметра, листу, њену величину и број за претрагу:

дефбинариСеарцх(арр, арр_сизе, сеарцх_нумбер):
 ниско = 0
 висока = величина_арр - 1
док ниско <= високо:
 средња = ниска + (висока-ниска)//2
 ако арр[мид] == број_претраге:
повратак мид
елиф арр[средина] > број_претраге:
 висока = средња - 1
друго:
 низак = средњи + 1
повратак-1

Иницијализујте две променљиве, ниско и висока, да служи као доња и горња граница листе. Слично Ц имплементацији, користите а док петља која сужава простор за претрагу. Иницијализујте мид за чување средње вредности листе. Питхон обезбеђује оператор дељења спрата (//) који обезбеђује највећи могући цео број.

Направите поређења и сузите простор за претрагу док средња вредност не буде једнака броју претраге. Ако број за претрагу није присутан, контрола ће се вратити -1.

арр_сизе = инт (инпут("Унесите број елемената: "))
арр=[]
штампа ("Унесите бројеве: ", енд="")
за и у опсегу (0,арр_сизе):
 арр.аппенд(инт(улазни()))
број_претраге = инт (унос("Унесите број за претрагу: "))
резултат = бинариСеарцх (арр, арр_сизе, сеарцх_нумбер)
ако је резултат == -1:
 штампа ("Број није присутан")
друго:
 принт("Број је присутан на позицији ", (резултат + 1))

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

Цалл бинариСеарцх() и пренети аргументе. Ако пронађете број, прикажите његову позицију или индекс, у супротном ће се појавити порука да број није присутан.

Излаз алгоритма бинарног претраживања

Следи излаз алгоритма бинарне претраге када је елемент присутан у низу:

Следећи је излаз алгоритма бинарне претраге када елемент није присутан у низу:

Научите основне структуре података и алгоритме

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

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