>> ZAMYLA CHAN: Първото нещо, което може известие за находка е, че ние вече
са код, написан за нас.
Това се нарича разпределение код.
Така че ние не сме просто писане нашата собствена кода от нулата вече.
Напротив, ние сме попълване на кухини в някои предварително съществуващ код.
>> Програмата find.c пита за номера за запълване на купа сено, търси в
Купа сено за потребител предостави игла, и да го прави това, като се обадите на сортиране и
търсене, функции, дефинирани в helpers.c.
Така find.c е писано вече.
Вашата задача е да се напише помощници.
>> И така, какво ще правим?
Ние сме за прилагане на две функции.
Search, която връща истина, ако стойността се намира в купа сено, връщайки
невярно, ако стойността е не в купа сено.
И след това ние сме също така прилагане на сортиране, който сортира масива нарича стойности.
Така че нека да се справи с търсенето.
>> Търси се изпълнява в момента като линейна търсене.
Но можете да направите много по-добре от това.
Линеен търсене се осъществява в О п време, което е доста бавно, въпреки че
може да търси всеки списък, дадено му.
Вашата работа е да се приложат двоично търсене, която тече в момента O на дневник п.
Това е доста бързо.
>> Но има една уговорка.
Binary търсене може да търси само чрез предварително сортирани списъци.
Защо е това?
Е, нека да разгледаме един пример.
Предвид масив от стойности, купа сено, ние ще трябва да се търси
игла, и в този Например, числото 3.
>> Начинът, по който двоично търсене работи е, че сравним средната стойност на
масива до иглата, който много прилича как ние отвори телефонния указател към средата
страница в Седмица 0.
Така че, след сравняване на средната стойност за иглата, можете да отхвърлите или на
лявата или дясната половина на масива чрез затягане на вашите граници.
В този случай, тъй като три, нашата игла, е по-малко от 10, средната стойност на
дясната граница може да се понижат.
>> Но опитайте се да направите вашите граници възможно най-стегнато.
Ако средната стойност не е иглата тогава знаете, че не е нужно да се
го включи в търсенето си.
Така че си прав обвързана да затегнете търсене границите съвсем малко повече,
и така нататък, и така нататък, докато да намерите вашата игла.
>> Така че това, което прави псевдо код изглежда?
Е, докато ние все още търсим чрез списъка и все още имат
елементи, за да търсите, ние приемаме средата от списъка и сравни, че
средната стойност за нашата игла.
Ако те са равни, тогава това означава, че ние имаме Намерени иглата, и ние можем да
връщане вярно.
>> В противен случай, ако иглата е по-малко от средната стойност, тогава това означава, че ние
може да се изхвърли в дясната половина и просто търсене на лявата страна на масива.
В противен случай, ние ще се търси в дясната част на масива.
И в края на краищата, ако не оказват повече елементи оставяли да търсите, но вие
не са намерили своя игла все още, След това се върнете фалшива.
Тъй като иглата определено не е в купа сено.
>> Сега, едно нещо, за чист този псевдо код в двоичен търсене е, че тя може да
да се тълкува или като един повтарящ или рекурсивно изпълнение.
Така че би било рекурсивно ако сте се обадили функцията за търсене в рамките на търсенето
функционира или половината от масива.
Ще разгледаме рекурсия малко по-късно в процеса.
Но знам, че това е опция ако искате да опитате.