Главна разлика између линеарног претраживања и бинарног претраживања је да бинарно претраживање траје мање времена за претраживање елемента из сортиране листе елемената. Стога се закључује да је ефикасност бинарног метода претраживања већа од линеарног претраживања.
Друга разлика је у томе што постоји предуслов за бинарно претраживање, тј. Елементи се морају сортирати, док у линеарном претраживању не постоји такав предувјет. Иако оба метода претраживања користе различите технике које су описане у наставку.
Цомпарисон Цхарт
| Основа за поређење | Линеарно претраживање | Бинари сеарцх |
|---|---|---|
| Тиме Цомплекити | НА) | О (лог 2 Н) |
| Најбоље време | Први елемент О (1) | Центар Елемент О (1) |
| Предуслов за низ | Но рекуиред | Низ мора бити сортиран |
| Најгори случај за Н број елемената | Потребна су Н поређења | Може закључити након само лог 2 Н поређења |
| Може се имплементирати на | Арраи и Линкед лист | Не може се директно имплементирати на повезану листу |
| Инсерт оператион | Лако се убацује на крај листе | Захтевајте обраду да бисте убацили на своје место да бисте задржали сортирану листу. |
| Алгоритхм типе | Итеративна по природи | Подијелите и освојите у природи |
| Корисност | Једноставан за употребу и нема потребе за било којим нарученим елементима. | Било како лукав алгоритам и елементи треба да буду организовани по реду. |
| Линије кода | Мање | Више |
Дефиниција линеарног претраживања
У линеарном претраживању, сваки елемент низа се дохваћа један по један у логичком реду и провјерава да ли је жељени елемент или не. Претрага ће бити неуспешна ако се приступи свим елементима, а жељени елемент неће бити пронађен. У најгорем случају, број просечног случаја можда ћемо морати да скенирамо половину величине поља (н / 2).
Према томе, линеарно претраживање се може дефинисати као техника која секвенцијално пролази кроз низ како би лоцирала дату ставку. Програм који је дат у наставку илуструје претраживање елемента низа помоћу претраживања.
Ефикасност линеарног претраживања
Потрошња времена или број поређења направљених у претраживању записа у табели претраживања одређује ефикасност технике. Ако је жељени запис присутан на првој позицији табеле за претрагу, тада се прави само једно поређење. Када је жељени запис последњи, потребно је направити н поређења. Ако је запис представљен негде у табели претраге, у просеку, број поређења ће бити (н + 1/2). Најгори случај ефикасности ове технике је О (н) за редослед извршења.
Ц Програм за претрагу елемента помоћу технике линеарне претраге.
#инцлуде #инцлуде воид маин () {инт а [100], н, и, итем, лоц = -1; цлрсцр (); принтф ("Унесите број елемента:"); сцанф ("% д", & н); принтф ("Унесите бројеве: н"); за (и = 0; и <= н-1; и ++) {сцанф ("% д", & а [и]); } принтф ("Унесите број за претрагу:"); сцанф ("% д", & итем); за (и = 0; и = 0) {принтф ("н% д се налази на позицији% д:", итем, лоц + 1); } елсе {принтф ("не постоји ставка"); } гетцх (); } Дефиниција бинарног претраживања
Бинарно претраживање је изузетно ефикасан алгоритам. Ова техника претраживања троши мање времена у претраживању дате ставке у минималним могућим поређењима. Да би извршили бинарно претраживање, прво морамо сортирати елементе низа.
Логика ове технике дата је у наставку:
- Прво, пронађите средњи елемент низа.
- Средњи елемент низа се пореди са елементом који се тражи.
Могу се појавити три случаја:
- Ако је елемент обавезни елемент, онда је претрага успешна.
- Када је елемент мањи од жељене ставке, претражите само прву половину поља.
- Ако је већи од жељеног елемента, претражите у другој половини поља.
Поновите исте кораке док се не пронађе неки елемент или не исцрпи у области претраге. У овом алгоритму, свака област претраживања времена се смањује. Због тога је број поређења највише лог (Н + 1). Као резултат тога, то је ефикасан алгоритам у поређењу са линеарним претраживањем, али се поље мора сортирати прије бинарног претраживања.
Ц Програм за проналажење елемента са бинарном техником претраживања.
#инцлуде воид маин () {инт и, бег, енд, миддле, н, сеарцх, арраи [100]; принтф ("Унесите број елемента"); сцанф ("% д", & н); принтф ("Унесите% д бројеве н", н); за (и = 0; и <н; и ++) сцанф ("% д", и низ [и]); принтф ("Унесите број за претрагу \ т сцанф ("% д", & претрага); бег = 0; крај = н - 1; средина = (бег + енд) / 2; вхиле (бег <= енд) {иф (низ [средњи] крај) принтф ("Претрага је неуспешна!% д није присутна на листи. \ т гетцх (); } Кључне разлике између линеарног претраживања и бинарног претраживања
- Линеарно претраживање је по природи итеративно и користи секвенцијални приступ. С друге стране, бинарна претрага примењује приступ поделе и осваја.
- Временска сложеност линеарног претраживања је О (Н), док бинарно претраживање има О (лог 2 Н).
- Најбоље вријеме у линеарном претраживању је за први елемент, тј. О (1). Насупрот томе, у бинарном претраживању, то је за средњи елемент, тј. О (1).
- У линеарном претраживању, најгори случај за претраживање елемента је Н број поређења. Насупрот томе, то је лог 2 Н број поређења за бинарно претраживање.
- Линеарно претраживање може бити имплементирано у низу, као иу повезаном попису, док бинарно претраживање не може бити имплементирано директно на повезану листу.
- Као што знамо Бинарно претраживање захтева сортирани низ који је разлог. Потребно је да обрада уметне на своје место да би се одржавала сортирана листа. Насупрот томе, линеарно претраживање не захтева сортиране елементе, тако да се елементи лако убацују на крај листе.
- Линеарно претраживање је једноставно за употребу и нема потребе за било којим нарученим елементима. С друге стране, алгоритам бинарног претраживања је ипак лукав, а елементи су нужно поредани у ред.
Закључак
Оба линеарна и бинарна алгоритма претраживања могу бити корисна у зависности од апликације. Када је низ података структура и елементи су поредани у сортираном редоследу, онда је бинарно претраживање пожељно за брзо претраживање. Ако је повезана листа структура података без обзира на то како су елементи распоређени, линеарно претраживање се усваја због недоступности директне имплементације бинарног алгоритма претраживања.
Типични бинарни алгоритам претраживања не може се користити за повезану листу јер је повезана листа динамична по природи и није познато гдје је средњи елемент заправо додијељен. Дакле, постоји потреба да се дизајнира варијација бинарног алгоритма претраге који може радити и на повезаном списку, јер је бинарно претраживање брже у извршењу од линеарног претраживања.
