Разлика између бинарне претраге и линеарне претраге

Бинарна претрага вс Линеарна претрага

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

Шта је линеарна претрага?

Линеарна претрага је најједноставнија метода претраживања, која сваки елемент на листи провјерава узастопно, све док не пронађе одређени елемент. Улаз у методу линеарног претраживања је редослед (као што су низ, колекција или низ) и ставка коју треба претраживати. Излаз је истинит ако је наведена ставка унутар датог низа или лажан ако није у низу. Будући да ова метода провјерава сваку ставку на листи док је пронађена наведена ставка, у најгорем случају ће проћи све елементе на листи прије него што пронађе потребан елемент. Сложеност линеарне претраге је о (н). Стога се сматра да је превише спор да би се користио при претраживању елемената на великим листама. Али то је врло једноставно и лакше имплементирати.

Шта је бинарна претрага?

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

Која је разлика између бинарне претраге и линеарне претраге?

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