[За възпроизвеждане на музика] 

ZAMYLA CHAN: Първото нещо, което може известие за находка е, че ние вече са код, написан за нас. Това се нарича разпределение код. Така че ние не сме просто писане нашата собствена кода от нулата вече. Напротив, ние сме попълване на кухини в някои предварително съществуващ код. 

Програмата find.c пита за номера за запълване на купа сено, търси в Купа сено за потребител предостави игла, и да го прави това, като се обадите на сортиране и търсене, функции, дефинирани в helpers.c. Така find.c е писано вече. Вашата задача е да се напише помощници. 

И така, какво ще правим? Ние сме за прилагане на две функции. Search, която връща истина, ако стойността се намира в купа сено, връщайки невярно, ако стойността е не в купа сено. И след това ние сме също така прилагане на сортиране който сортира масива нарича стойности. 

Така че нека да се справи с търсенето. Търсене в момента е реализиран като линейно търсене, но можете да направите много по-добро от това. Linear търсене се осъществява в O п време, което е доста бавно. Въпреки, че може да търси всеки списък, дадено му. Вашата работа е да се приложат двоично търсене, която тече в момента O на дневник п. Това е доста бързо. 

Но има една уговорка. Binary търсене може да търси само чрез предварително сортирани списъци. Защо е това? 

Ами нека да разгледаме един пример. Предвид масив от стойности, купа сено, ние ще трябва да се търси игла. И в този пример, числото три. Начинът, по който двоично търсене работи е, че сравним средната стойност на масива до иглата, който много прилича как отворихме телефонния указател до средата страница в нула седмица. 

Така че, след сравняване на средната стойност за иглата, можете да отхвърлите или на лявата или дясната половина на масива чрез затягане на вашите граници. В този случай, тъй като три, нашата игла, е по-малко от 10, като средната стойност на дясната граница може да се понижат. Но опитайте се да направите вашите граници възможно най-стегнато. Ако средната стойност не е иглата тогава знаете, че не е нужно да се го включи в търсенето си. Така че си прав граница може да затегнете търсене границите съвсем малко повече, и така нататък, и така нататък, докато да намерите вашата игла. 

Така че какво прави pseudocode изглежда? Е, докато ние все още търсим чрез списъка и все още има елементи към търсите, ние приемаме по средата на списъка, и сравни, че средната стойност на нашата игла. Ако те са равни, тогава това означава, че ние имаме Намерени иглата и можем връщане вярно. 

В противен случай, ако иглата е по-малко от средната стойност, тогава това означава, че ние може да се изхвърли в дясната половина, а само търсене на лявата страна на масива. В противен случай, ние ще се търси в дясната част на масива. И в края на краищата, ако не оказват повече елементи оставяли да търсите, но вие не са намерили своя игла все още, тогава ще връщане фалшиви защото иглата определено не е в купа сено. 

Сега чист нещо за този pseudocode в двоичен търсене е, че тя може да бъде тълкува или като един повтарящ или рекурсивно изпълнение. Така че би било рекурсивно ако сте се обадили функцията за търсене в рамките на търсенето функционира или половината от масива. Ще разгледаме рекурсия малко по-късно през Разбира се, но знам, че това е опция, ако искате да опитате. 

Сега нека да разгледаме вид. Sort отнема масив и цялото число п, което е дължината на масива. Сега има различни видове на видове, както и да разгледаме някои шорти за демонстрации и обяснения. Типът на възвръщаемост за нашите подреди функция е невалидна. Така че това означава, че ние не отиваме да се върнат всеки масив от сортиране. Ние всъщност няма да се промени самото масив, който е приет в нас. 

И това е възможно, тъй като масиви са предават по референция C. Сега ще вижте повече за това по-късно, но съществена разлика между преминаване в нещо като число и преминаване в масив, е, че когато премине в цяло число, C е просто ще направи копие на този число и преминават да функцията. Оригиналната стойност няма да се промени веднъж функцията е завършен. С масив, от друга страна, това е няма да направи копие, и ще всъщност да се редактира Самият много масив. 

Така че един вид вид е вида избор. Подреди подбор работи като започнете началото, а след това ви обхождане над и да намерят най-малкия елемент. И тогава вие сменяте, че най-малкият елемент с първия. И тогава ще се премине към втория елемент , Намери следващата по-малка елемент, а след това сменяте, че с втори елемент в масива защото първият елемент вече сортирани. И така, след това да продължите за всеки елемент за идентифициране на най-малките стойност и да го замените. 

Защото е равна на 0, на много първи елемент до п минус 1, ти започваш да се сравни всяка следваща стойност след това и да намерят индексът на минималната стойност. След като се намери индексът на минимална стойност, можете да сменяте, че стойността на масив минимум и масив I. 

Друг вид на вид, че можете да изпълнение е балон вид. Така балон подреди итерации над списъка сравняване на съседни елементи и смяна на елементи, които са в грешен ред. И по този начин, най-големият елемент ще балон до края. И списъкът се сортира, след не повече елементи са били разменени. 

Така че тези, които са два примера за сортиране алгоритми, които можете да приложат за програмата находка. След като приключите сортиране, и сте извършва търсене, сте готови. Моето име е Zamyla, и това е CS50. 

[За възпроизвеждане на музика]