ZAMYLA CHAN: Првото нешто што може да известување за откритие е дека ние веќе се код напишан за нас. Ова се нарекува дистрибуција код. Значи ние не сме само пишување нашите сопствени кодот од нула повеќе. Наместо тоа, ние сме пополнување на празнини во некои постоечки код. 

На find.c програмата го поттикнува за броеви да се пополни стогот, пребарувања haystack за поднесено корисникот игла, и тоа го прави ова со повикување вид и пребарување, функции дефинирани во helpers.c. Па find.c е напишано веќе. Вашата работа е да се напише помагачи. 

Па што правиме ние? Ние сме спроведување на две функции. Барај, кој враќа true ако вредност се наоѓа во стогот, враќајќи се лажни ако вредноста е не во haystack. А потоа ние сме, исто така, спроведување вид, Кои видови на низа наречен вредности. Па ајде да се справи пребарување. 

Барај во моментов е имплементиран како линеарна пребарување. Но можете да направите многу подобро од тоа. Линеарно пребарување се спроведува во О од n време, што е сосема бавно, иако тоа може да се бара било која листа дадена на него. Вашата работа е да се имплементира бинарни пребарување, кој ја стартувате време О на најавите n. Тоа е доста брзо. 

Но, има една одредба. Бинарни пребарување само да направите пребарување преку пред-сортирани листи. Зошто е тоа така? Добро, ајде да погледнеме еден пример. Дадени низа од вредности, стогот, ние ќе треба да се бараат игла, и во оваа пример, број 3. 

Начинот на кој бинарни пребарување работи е дека ја споредиме на средната вредност на низата на игла, многу сличен како ние отвори телефонски именик до средината страница во недела 0. Па по споредување на средната вредност за иглата, можете да ги отфрлите или лево или десната половина на низата со затегнување на вашиот границите. Во овој случај, бидејќи 3, нашите игла, е помалку од 10, на средната вредност, на право врзани може да се намали. 

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

Значи она што го прави псевдо код изгледа? Добро, додека ние сме сè уште во потрага преку листата и се уште имаат елементи за да се погледне во, ние се средината на листата и споредете дека Средната вредност на нашите игла. Ако тие се еднакви, тогаш тоа значи дека ние сме најде игла, и можеме да врати вистина. 

Инаку, ако иглата е помала од средната вредност, тогаш тоа значи дека ние може да ги отфрлите десната половина и само пребарување на левата страна на низата. Инаку, ние ќе се бара десната страна на низа. И на крајот, ако не имате било какви повеќе елементи што останале да пребарување, но ќе не најдов вашиот игла сепак, тогаш ќе се вратите лажна. Бидејќи иглата дефинитивно не е во haystack. 

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