>> [MUSIC nagpe-play]
>> ZAMYLA Chan: Ang unang bagay na maaari mong paunawa tungkol sa find ay na namin na
na-code na isinulat para sa amin.
Ito ay tinatawag na code sa pamamahagi.
Kaya hindi lang kami ay sumusulat ating sariling code mula sa simula ngayon.
Sa halip, kami ay pagpuno sa voids sa ilang mga pre-umiiral na code.
>> Ang programa ng find.c prompt para sa mga numero ng upang punan ang mandala ng dayami, ang mga paghahanap ang
mandala ng dayami para sa isang isinumite ng gumagamit karayom, at gagawin nito ito sa pamamagitan ng pagtawag uri at
paghahanap, mga pag-andar na tinukoy sa helpers.c.
Kaya find.c ay nakasulat na.
Ang iyong trabaho ay sumulat ng Katulong.
>> Kaya kung ano ang ginagawa namin?
Kami ay pagpapatupad ng dalawang mga pag-andar.
Paghahanap, na nagbabalik totoo kung ang isang halaga ay natagpuan sa mandala ng dayami, bumabalik
hindi totoo kung ang halaga ay wala sa mandala ng dayami.
At pagkatapos kami ay pagpapatupad ring uri aling uri ang array na tinatawag na mga halaga.
>> Kaya pagharap sa isang bagay ng paghahanap ipaalam.
Search ay kasalukuyang ipinapatupad bilang isang linear na paghahanap, ngunit maaari mong gawin magkano
mas mahusay kaysa sa na.
De-sa paghahanap ay ipinapatupad sa Oh ng n oras, na kung saan ay masyadong mabagal.
Bagaman, maaari itong hanapin anumang mga listahan na ibinigay dito.
Ang iyong trabaho ay ang ipatupad ang binary paghahanap, kung saan tumakbo na oras O ng log n.
Iyon ay medyo mabilis.
>> Subalit mayroong isang tadhana.
Maaari lamang maghanap ng binary paghahanap sa pamamagitan ng pre-pinagsunod-sunod ng mga listahan.
Bakit na?
>> Tingnan natin ang isang halimbawa Well ipaalam.
Given isang array ng mga halaga, ang mandala ng dayami, kami ay pagpunta sa tumitingin
para sa isang karayom.
At sa halimbawang ito, ang integer tatlo.
Ang paraan na gumagana ang binary paghahanap ay na ihambing namin ang gitnang halaga ng
ang array sa karayom, halos tulad ng kung paano binuksan namin ang isang phonebook sa gitna
pahina sa linggo zero.
>> Kaya pagkatapos ng paghahambing sa gitna ng halaga sa ang karayom, maaari mong itapon ang alinman sa
kaliwa o kanan kalahati ng array sa pamamagitan ng apreta ang iyong mga hanggahan.
Sa kasong ito, dahil tatlong, ang aming karayom, Mas mababa sa 10, sa gitna halaga, ang
maaaring bumaba karapatan tumalbog.
Ngunit subukan upang gawin ang iyong mga hanggahan bilang masikip hangga't maaari.
Kung sa gitna halaga ay hindi ang karayom, pagkatapos ay alam mo na hindi mo kailangang
isama ito sa iyong paghahanap.
Kaya ikaw ay kanan nakatali Maaari higpitan ang hanggahan sa paghahanap lamang ng isang maliit na maliit bit higit pa,
at iba pa at iba pa hanggang sa mo mahanap ang iyong mga karayom.
>> Kaya kung ano ang hitsura ng pseudocode tulad?
Well habang pa rin kaming naghahanap sa pamamagitan ng ang listahan at mayroon pa ring mga elemento sa
tumingin sa, tumagal kami sa gitna ng listahan, at ihambing na gitna ng halaga sa
ang aming karayom.
Kung hindi nila ito katumbas, pagkatapos ay nangangahulugan na hindi namin natagpuan ang karayom ​​at kaya namin
nagbabalik ng tunay.
>> Kung hindi man, kung ang karayom ​​ay mas mababa sa sa gitna halaga, pagkatapos ito ay nangangahulugan na namin
Maaari itapon ang mga karapatan kalahati, at lamang maghanap sa kaliwang bahagi ng array.
Kung hindi man, gagamitin namin maghanap sa kanang bahagi ng array.
At sa dulo, kung wala kang anumang higit pang mga elemento sa kaliwa upang maghanap ngunit ikaw
hindi pa natagpuan ang iyong mga karayom, pagkatapos mo bumalik hindi totoo dahil ang karayom
Talagang ay wala sa mandala ng dayami.
>> Ngayon isang kapong baka bagay tungkol sa ito pseudocode sa binary paghahanap ay na maaari itong maging
kahulugan bilang alinman sa isang umuulit o recursive pagpapatupad.
Kaya magiging recursive kung tinatawag mo ang pag-andar ng paghahanap sa loob ang paghahanap
gumana sa alinman sa kalahati ng array.
Tatalakayin namin ang recursion ng kaunti mamaya sa Siyempre, ngunit alam na ito ay isang
opsyong ito kung gusto mong subukan.
>> Ngayon tingnan natin ang uri ipaalam.
Pagbukud-bukurin tumatagal ng isang array at ang integer n, kung saan ay ang laki ng array.
Ngayon may mga iba't-ibang mga iba't ibang mga uri ng mga uri, at maaari kang tumingin sa ilang mga
shorts para sa mga demo at mga paliwanag.
Ang uri ng return para sa aming mga sort function na ay walang bisa.
Kaya ibig sabihin nito ay na hindi namin pagpunta maibalik ang anumang mga array mula sa uri.
Talaga kami ng pagpunta upang baguhin ang napaka array na ay pumasa sa sa amin.
>> At na posible dahil array ay pumasa sa pamamagitan ng sanggunian sa C. Ngayon namin makikita
tingnan ang higit pa tungkol ito sa ibang pagkakataon, ngunit ang mahahalagang pagkakaiba sa pagitan ng nagdaraan
sa isang bagay tulad ng isang integer at nagdaraan sa isang array, ay na kapag nag-
pumasa sa isang integer, C ay pagpunta lamang sa gumawa ng kopya ng na integer at pumasa sa
ito sa function.
Ang orihinal na variable ay hindi mababago sa sandaling ang function ay tapos na.
Gamit ang isang array, sa kabilang banda, ito ay hindi pagpunta sa gumawa ng kopya, at idedetalye mo
talaga mai-e-edit ang napaka mismo ng array.
>> Kaya isang uri ng pag-uuri ay ang uri pagpili.
Nagsisikap ang uri pagpili sa pamamagitan ng simula sa sa simula, at pagkatapos ay umulit sa iyo
sa ibabaw at hanapin ang pinakamaliit na elemento.
At pagkatapos ay magpalit ka na pinakamaliit elemento na may unang isa.
At pagkatapos lumipat ka sa pangalawang elemento , Hanapin ang susunod pinakamaliliit
elemento, at pagkatapos ay magpalit na may mga pangalawang elemento sa array dahil
sa unang elemento ay naka-pinagsunod-sunod.
At kaya pagkatapos ay magpatuloy sa iyo para sa bawat sangkap sa pagkilala sa mga pinakamaliliit na
halaga at pagpapalit ito.
>> Para sa katumbas ko 0, ang pinakaunang elemento sa n minus 1, ikaw ay pagpunta sa ihambing
bawat susunod na halaga matapos na at malaman sa index ng minimum na halaga.
Sa sandaling makita mo ang index ng minimum na halaga, Maaari mong magpalit na halaga ng array
minimum at array I.
>> Ang isa pang uri ng pag-uuri na maaari mong ipatupad ang bubble sort.
Kaya bubble uri iterates sa ibabaw ng listahan paghahambing ng magkakaharap na mga elemento at mga
pagpapalit ang mga elemento na ay nasa maling pagkakasunud-sunod.
At sa ganitong paraan, ang pinakamalaking elemento nasain bubble sa dulo.
At ang listahan ay pinagsunod-sunod sa sandaling walang higit pa mga elemento ay nai-swapped.
>> Kaya mga dalawang mga halimbawa ng mga uri algorithm na maaari mong ipatupad para sa
ang programa find.
Sa sandaling natapos mo ang pag-uuri, at ikaw ay tapos na paghahanap, tapos ka.
Ang pangalan ko ay Zamyla, at ito ay CS50.
>> [MUSIC nagpe-play]