[Музыка гуляе] 

ZAMYLA Чан: Першае, што вы маглі б апавяшчэнне аб знаходцы з'яўляецца тое, што мы ўжо ўжо код, напісаны для нас. Гэта называецца код размеркаванне. Такім чынам, мы не толькі напісанне ўласнай код з нуля больш. Хутчэй, мы запаўнення пустэч у некаторым папярэдне існуючага кода. 

Праграма find.c запытвае нумары запоўніць стог сена, пошук стозе сена для карыстальнікаў прадстаўленых іголкі, і ён робіць гэта шляхам выкліку роду і пошуку, функцыі, пэўныя у helpers.c. Так find.c напісана ўжо. Ваша задача напісаць памочнікаў. 

Так што мы робім? Мы рэалізацыі дзве функцыі. Пошук, які вяртае ісціну, калі значэнне знаходзіцца ў стозе сена, вяртаючыся ілжывым, калі значэнне не ў стозе сена. А потым мы таксама ажыццяўляе роду якая сартуе масіў з імем значэння. 

Так што давайце вырашаць пошуку. Пошук у цяперашні час рэалізавана ў выглядзе лінейны пошук, але вы можаце зрабіць значна лепш, чым гэта. Лінейны пошук ажыццяўляецца ў O часу н, які з'яўляецца даволі павольным. Хоць, ён можа шукаць любой спіс дадзена яму. Ваша задача заключаецца ў рэалізацыі бінарны пошук, які падчас выканання O з часопіса п. Гэта даволі хутка. 

Але ёсць агаворка. Двайковага пошуку можна толькі пошук праз папярэдне парадку п. спісаў. Чаму гэта адбываецца? 

Ну давайце паглядзім на прыкладзе. Улічваючы масіў значэнняў, стог сена, мы збіраемся шукаць іголкі. І ў гэтым прыкладзе цэлае тры. Такім чынам, што бінарны пошук працуе так, што мы параўнаем сярэдні кошт масіў да іголкі, гэтак жа, як, як мы адкрылі тэлефонную кнігу на сярэдзіне старонкі ў нулявым тыдзень. 

Такім чынам, пасля параўнання сярэдняе значэнне для іголка, вы можаце адмовіцца ад альбо налева або правая палова масіва зацягнуўшы свае межы. У гэтым выпадку, так як тры, наша іголка, менш за 10, сярэдняе значэнне, Права мяжа можа змяншацца. Але паспрабаваць зрабіць вашыя мяжы як мага шчыльней. Калі сярэдняе значэнне не іголка, то вы ведаеце, што вам не трэба, каб ўключыць яго ў гэтай катэгорыі. Такім чынам, вы маеце рацыю мяжа можа зацягнуць пошук мяжы ледзь-ледзь больш, і гэтак далей і таму падобнае да вы знайшлі іголку. 

Такім чынам, што ж псевдокод выглядаць? Ну а мы ўсё яшчэ праглядаючы спіс і да гэтага часу элементы глядзець у, мы бярэм сярэдзіну спісу, і параўнаць, што сярэдняе значэнне для наша іголка. Калі яны роўныя, то гэта азначае, што мы ў знайшла іголку, і мы можам вярнуцца дакладна. 

У адваротным выпадку, калі іголка менш сярэдняе значэнне, тое, што азначае, што мы можна адкінуць правую палову, і проста пошук па левы бок масіва. У адваротным выпадку, мы будзем шукаць Правая частка масіва. І ў канцы, калі вы не маеце любыя больш элементаў злева пошук, але вы Нічога не знайшлі іголку яшчэ, то вы вярнуцца ілжывым, таму што іголка дакладна не ў стозе сена. 

Зараз акуратна рэч пра гэта псевдокоде у двайковага пошуку з'яўляецца тое, што ён можа быць інтэрпрэтаваць як альбо паўтаральны або рэкурсіўная рэалізацыя. Таму было б рэкурсіўным, калі вы назвалі функцыя пошуку ў пошуку функцыянаваць па абодва паловы масіва. Мы разгледзім рэкурсіі крыху пазней у Вядома, але ведаю, што гэта варыянт, калі вы хочаце паспрабаваць. 

Зараз давайце паглядзім на роду. Сартаваць прымае масіў і цэлае п, што памер масіва. Зараз ёсць розныя тыпы ў духу, і вы можаце глядзець на некаторыя шорты для дэманстрацый і тлумачэнняў. Які вяртаецца тып для нашага Функцыя сартавання, з'яўляецца нікчэмным. Дык гэта значыць, што мы не збіраемся вярнуцца любы масіў з роду. Мы на самой справе збіраецца мяняць вельмі Масіў, які быў прыняты ў нас. 

І гэта магчыма, таму што масівы перадаюцца па спасылцы ў С. Цяпер мы гл. пра гэта крыху пазней, але Істотнае адрозненне паміж перадачай у чымсьці накшталт цэлае і праходжання ў масіве, у тым, што, калі вы перайсці ў цэлы лік, C толькі збіраецца зрабіць копію гэтага цэлага і перадаць яго функцыі. Арыгінальны пераменная не будзе зменена Пасля таго, як функцыя скончаная. З масіва, з другога боку, гэта не збіраецца рабіць копію, і вы будзеце фактычна рэдагавання Сам вельмі масіў. 

Так адзін тып роду з'яўляецца выбар роду. Выбар роду працуе, пачынаючы з пачатак, а затым ітэрацыі зноў і знайсці найменшы элемент. І тады вы памяняць, што маленькі элемент з першай. А потым вы пераходзіце на другі элемент , Знайсці наступны па велічыні элемент, а затым памяняць, што з Другі элемент у масіве, так як першы элемент ўжо адсартаваныя. І так, то вы па-ранейшаму для кожнага элементам у працэсе выяўлення самых маленькіх значэнне і замены яго. 

Бо я роўная 0, самы першы элемент п мінус 1, вы збіраецеся параўноўваць кожны наступны значэнне пасля гэтага і знайсці індэкс мінімальнага значэння. Як толькі вы знойдзеце індэкс мінімальнага значэння, вы можаце памяняць гэта значэнне масіва Мінімальны і масіў І. 

Іншы тып роду, што вы можаце рэалізаваць гэта пузырьковый сартавання. Так пузырьковый сартавання перабірае спіс параўнанні суседніх элементаў і перапампоўкі элементы, якія знаходзяцца ў няправільным парадку. І такім чынам, найбольшы элемент будзе тапырыцца да канца. ня І спіс сартуецца раз не больш элементы былі замененыя. 

Такім чынам, гэта два прыкладу роду алгарытмы, якія можна рэалізаваць для праграма знаходка. Як толькі вы скончыце роду, і ў цябе зроблена пошуку, вы скончыце. Мяне клічуць Zamyla, і гэта CS50. 

[Музыка гуляе]