>> ЗАМИЛА цхан: Прва ствар коју би могао Обавештење о налаза је да смо већ
су код написан за нас.
Ово се назива дистрибуција код.
Дакле, ми не само писање наше више Код са нуле.
Уместо тога, ми смо попуњавање празнина у неком већ постојећом шифром.
>> Финд.ц Програм пита за бројеве да попуни пласту сена, тражи
пласту сена за корисника подноси игле, и то чини овај позивом врсту и
сеарцх, функције дефинисане у хелперс.ц.
Дакле финд.ц је написано већ.
Ваш посао је да пишем помагаче.
>> Дакле, шта ми радимо?
Ми спровођење две функције.
Претрага, који враћа труе ако вредност се налази у пласту сена, враћа
фалсе ако је вредност не у пласту сена.
И онда смо такође спроводи сортирање, који сортира низ називом вредности.
Па хајде да се позабаве претрагу.
>> Тражи се тренутно спроводи као линеарну претрагу.
Али можете да урадите много боље од тога.
Линеарно претраживање се спроводи у О од н време, што је прилично споро, мада
може да тражи било какву листу дато.
Ваш посао је да спроведе бинарну претрагу, који је остао од времена О лог н.
То је прилично брзо.
>> Али постоји одредба.
Бинарни претраживање може само тражење кроз унапред сортираних листама.
Зашто је то тако?
Па, погледајмо пример.
Имајући у виду низ вредности, пласту сена, ћемо бити у потрази
за игле, и у овом на пример, цео број 3..
>> Начин на који ради је бинарна претрага да упоредимо средњу вредност
низ на игле, много ми се како отворили смо телефонски именик на средини
страна у Недељи 0.
Дакле, након поређења средњу вредност игла, можете одбаците или
лево или десно половини низа пооштравањем своје границе.
У овом случају, од 3, наша игла, је мање од 10, средња вредност,
Право граница може смањити.
>> Али покушајте да направите границе као чврсто могуће.
Ако средња вредност није игла, онда знате да не морате да
укључити га у претрагу.
Дакле, ваше право везан може затегнути Претрага границе само мали мало више,
и тако даље и тако даље, све док сте пронашли своју иглу.
>> Дакле, шта псеудо код изгледа?
Па, док смо још увек гледа кроз листа и даље имају
елементи за изгледају у, узмемо средину листе и упоредите то
средња вредност за наше уши.
Ако су једнаки, онда то значи да смо нашао иглу, и можемо
ретурн труе.
>> У супротном, ако игла мање од средња вредност, онда значи да смо
може одбацити праву половину и само Претраживач леву страну низа.
У супротном, ми ћемо претрагу десна страна низа.
И на крају, ако не имати било више елемената лева за претраживање, али вам
нису пронашли своју иглу још, онда се вратите лажна.
Зато игла дефинитивно није у пласту сена.
>> Сада, један уредан ствар у вези овог псеудо код у бинарном потрази је да он може да
тумачити као било итеративни или рекурзивно имплементација.
Дакле, било би рекурзивна ако зове функција претраге у потрази
функционисати на било половини низа.
Ми ћемо покрити рекурзије мало касније у току.
Али знам да је то опција ако желите да испробате.