Садржај

• Упоредни графикон
• Дефиниција линеарне претраге
• Дефиниција бинарне претраге
• Закључак

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

Главна разлика између линеарне претраге и бинарне претраге јесте да је бинарном претраживању потребно мање времена за претраживање елемента из сортиране листе елемената. Дакле, закључује се да је ефикасност метода бинарног претраживања већа од линеарне претраге.

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

1. Упоредни графикон
2. Дефиниција
3. Кључне разлике
4. Закључак

Упоредни графикон

Основе за поређење	Линеарна претрага	Бинарна претрага
Временска сложеност	НА)	О (записник) 2 Н)
Најбоље време за случај	Први елемент О (1)	Средишњи елемент О (1)
Предуслов за низ	Није потребно	Низ мора бити поређен редоследом
Најгори случај за Н број елемената	Н поређења није потребно	Може се закључити након само дневника2Н поређења
Може се имплементирати на	Листа арраи и повезаних	Не може се директно имплементирати на повезаној листи
Уметните операцију	Лако се убацује на крају листе	Захтијевајте обраду да бисте је уметнули на свом одговарајућем месту да бисте одржавали сортирану листу.
Тип алгоритма	Итеративне природе	Поделите се и освојите у природи
Корисност	Једноставан је за употребу и нема потребе за било којим нарученим елементима.	У сваком случају, сложени алгоритам и елементи требају бити организовани по редоследу.
Кодекси линија	Мање	Више

Дефиниција линеарне претраге

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

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

Ефикасност линеарне претраге

Потрошња времена или број упоређивања приликом претраживања записа у табели за претрагу одређује ефикасност технике. Ако је жељени запис присутан на првом месту табеле за претрагу, тада се врши само једно упоређивање. Кад је жељени запис последњи, тада треба да се направи н упоређивање. Ако ће се запис представити негде у табели за претрагу, у просеку ће бити упоређен број упоређивања (н + 1/2). Најгора ефикасност ове технике је да О (н) означава редослед извођења.

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

#инцлуде #инцлуде воид маин () {инт а, н, и, ставка, лоц = -1; цлрсцр (); ф (" нУнесите број елемента:"); сцанф ("% д", & н); ф ("Унесите бројеве: н"); за (и = 0; и <= н-1; и ++) {сцанф ("% д", & а); } ф (" нУнесите број који се тражи:"); сцанф ("% д", и ставка); за (и = 0; и <= н-1; и ++) {иф (ставка == а) {лоц = и; пауза; }} иф (лоц> = 0) {ф (" н% д се нађе у положају% д:", ставка, лоц + 1); } елсе {ф (" н Ставка не постоји"); } гетцх (); }

Дефиниција бинарне претраге

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

Логика иза ове технике је дата у наставку:

• Прво пронађите средњи елемент низа.
• Средњи елемент матрице је упоређен са елементом који се тражи.

Могу се појавити три случаја:

1. Ако је елемент потребан елемент, тада је претрага успјешна.
2. Кад је елемент мањи од жељеног елемента, претражите само прву половину поља.
3. Ако је већи од жељеног елемента, претражите у другој половици поља.

Понављајте исте кораке док се елемент не нађе или не исцрпи у подручју претраге. У овом алгоритму се свако време претраживања смањује. Стога је број поређења највише лог (Н + 1). Као резултат тога, то је ефикасан алгоритам у поређењу са линеарном претрагом, али низ се мора сортирати пре него што се изврши бинарна претрага.

Ц Програм пронаћи елемент помоћу бинарне технике претраживања.

#инцлуде воид маин () {инт и, бег, крај, средина, н, претрага, низ; ф ("Унесите број елемента н"); сцанф ("% д", & н); ф ("Унесите% д бројеве н", н); за (и = 0; и <н; и ++) сцанф ("% д", & низ); ф ("Унесите број за претраживање н"); сцанф ("% д" и претрага); бег = 0; крај = н - 1; средња = (бег + крај) / 2; док је (бег <= крај) {иф (низ <сеарцх) бег = средњи + 1; друго ако (арраи == сеарцх) {ф ("Претрага је успешна. н% д пронађена на локацији% д. н", претрага, средина + 1); пауза; } елсе енд = средина - 1; средња = (бег + крај) / 2; } иф (бег> енд) ф ("Претрага је неуспешна!% д није присутна на листи. н", претрага); гетцх (); }

1. Линеарна претрага је итеративне природе и користи секвенцијални приступ. С друге стране, Бинарна претрага примењује приступ подели и освоји.
2. Временска сложеност линеарне претраге је О (Н), док бинарна претрага има О (дневник)₂Н).
3. Најбоље вријеме случаја у линеарној претрази је за први елемент, тј. О (1). Супротно томе, код бинарне претраге то је за средњи елемент, тј. О (1).
4. У линеарној претрази, најгори случај за претрагу елемента је Н број поређења. Супротно томе, то је дневник₂Н број поређења за бинарну претрагу.
5. Линеарна претрага може се имплементирати у низу као и на повезаној листи док се бинарна претрага не може спровести директно на повезаној листи.
6. Као што знамо, бинарна претрага захтева сортирани низ који је разлог због којег је потребна обрада да би се уметнула на њено одговарајуће место да би одржала сортирану листу. Супротно томе, линеарно тражење не захтева сортиране елементе, па се елементи лако убацују на крају листе.
7. Линеарна претрага је једноставна за употребу и нема потребе за било којим нарученим елементима. С друге стране, алгоритам бинарног претраживања ипак је лукав, а елементи су нужно распоређени по редоследу.

Закључак

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

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