[Музички] 

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

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

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

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

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

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

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

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

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

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

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

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

Така еден вид на вид е вид селекција. Вид на селекција работи со почеток во на почетокот, а потоа ќе iterate над и да се најде најмалиот елемент. А потоа ќе трампа дека најмалите елемент со првиот. А потоа ќе се преселат во вториот елемент , Се најде на следната најмалиот елемент, а потоа се разменуваат дека со Вториот елемент во низата бидејќи првиот елемент е веќе подредени. И така, тогаш ќе продолжи за секој елемент во идентификување на најмалите вредност и Замена на тоа надвор. 

Зашто Јас еднаква на 0, првиот елемент до n минус 1, си оди за да се споредат секој нареден вредност после тоа и да се најде индексот на минималната вредност. Откако ќе се најдат на индексот минималната вредност, можете да го трампа дека вредноста на низа минимум и низа I. 

Друг тип на вид што можете да спроведување е балон вид. Значи меур вид iterates преку листа споредување соседните елементи и Замена на елементи кои се во погрешна цел. И на овој начин, најголемиот елемент ќе меур до крај. И листата е сортирана еднаш не повеќе елементи биле заменети. 

Значи тоа се два примери на сортирање алгоритми кои може да се спроведе за програмата најдете. Откако ќе завршите вид, и сте направи за пребарување, ќе завршиш. Моето име е Zamyla, а тоа е CS50. 

[Музички]