[Music kucheza] 

ZAMYLA CHAN: Jambo la kwanza nguvu ilani kuhusu kupata ni kwamba tayari kuwa kanuni zilizoandikwa kwa ajili yetu. Hii inaitwa usambazaji code. Hivyo sisi siyo tu kuandika yetu wenyewe kanuni kutoka mwanzo tena. Badala yake, sisi ni kujaza katika voids katika baadhi ya kanuni kabla ya zilizopo. 

mpango find.c papo kwa idadi kujaza haystack, utafutaji haystack kwa mtumiaji in sindano, na haina kwa kuita aina na search, kazi inavyoelezwa katika helpers.c. Hivyo find.c imeandikwa tayari. Kazi yako ni kuandika kuwanusuru. 

Basi ni nini sisi kufanya? Sisi ni utekelezaji wa kazi mbili. Search, ambayo anarudi kweli kama thamani hupatikana katika haystack, kurudi uongo kama thamani ni si katika haystack. Na kisha sisi ni pia kutekeleza aina ambayo aina safu kuitwa maadili. 

Basi hebu kukabiliana na search. Search kwa sasa ni kutekelezwa kama search linear, lakini unaweza kufanya mengi bora kuliko hiyo. Search linear unatekelezwa katika O ya n wakati, ambayo ni polepole kabisa. Pamoja na kwamba, unaweza kutafuta orodha wowote yake. Kazi yako ni kutekeleza search binary, ambayo ina kukimbia wakati O logi n. Hiyo ni pretty haraka. 

Lakini kuna ahadi. Search kisha unaweza tu kutafuta kwa njia ya orodha kabla ya yamepangwa. Kwa nini ni kwamba? 

Naam hebu tuangalie mfano. Kutokana na safu ya maadili, haystack, tunakwenda kuwa na kuangalia kwa sindano. Na katika mfano huu, integer tatu. njia ambayo search binary kazi ni kuwa sisi kulinganisha thamani katikati ya safu ya sindano, kama ilivyo kwa jinsi sisi kufunguliwa phonebook katikati ukurasa katika wiki sifuri. 

Hivyo, baada ya kulinganisha thamani ya katikati ya sindano, unaweza kuondokana na ama upande wa kushoto au nusu wa kulia wa safu na inaimarisha mipaka yako. Katika kesi hiyo, tangu tatu, sindano yetu, ni chini ya 10, thamani ya kati, haki amefungwa unaweza kupungua. Lakini kujaribu kufanya mipaka yako kama tight kama iwezekanavyo. Kama thamani katikati ni si sindano, kisha unajua kwamba hawana haja ya ni pamoja na katika utafutaji wako. Basi, wewe ni haki amefungwa unaweza kaza mipaka search tu kidogo kidogo zaidi, na kadhalika na kadhalika mpaka kupata sindano yako. 

Basi ni nini pseudocode kuangalia kama? Vizuri wakati bado tuko kutafuta njia ya orodha na bado na mambo ya kuangalia katika, sisi kuchukua katikati ya orodha, na kulinganisha kwamba thamani katikati ya sindano yetu. Kama uko sawa, basi hiyo ina maana tumekuwa kupatikana sindano na tunaweza kurudi kweli. 

Vinginevyo, kama sindano ni chini ya thamani katikati, basi hiyo ina maana sisi unaweza kuondokana na nusu ya haki, na tu kutafuta upande wa kushoto wa safu. Vinginevyo, tutaweza kutafuta upande wa safu ya haki. Na mwisho, kama wewe huna lolote mambo zaidi wa kushoto na kutafuta lakini sikuona sindano yako bado, basi kurudi uongo kwa sababu sindano dhahiri si katika haystack. 

Sasa jambo nadhifu kuhusu pseudocode hii katika kutafuta binary ni kwamba inaweza kuwa kufasiriwa kama ama iterative au utekelezaji kujirudia. Hivyo itakuwa kujirudia kama wewe kuitwa kutafuta kazi ndani ya search kazi ama nusu ya safu. Tutaweza cover kujirudia kidogo baadaye katika Bila shaka, lakini tunajua kwamba ni chaguo kama Ningependa kujaribu. 

Sasa hebu tuangalie aina. Aina inachukua safu na integer n, ambayo ni ya kawaida ya safu. Sasa kuna aina mbalimbali tofauti wa kila aina, na unaweza kuangalia baadhi kaptula kwa demos na maelezo. kurudi aina kwa ajili yetu aina ya kazi ni batili. Hivyo hiyo ina maana kwamba sisi siyo kwenda kurudi safu yoyote kutoka aina. Sisi ni kweli kwenda na mabadiliko sana safu kwamba ilipitishwa ndani yetu. 

Na kwamba inawezekana kwa sababu arrays ni kupita kwa kumbukumbu katika C. Sasa tutaweza kuona zaidi kuhusu hili baadaye, lakini tofauti muhimu kati ya kupita katika kitu kama integer na kupita katika safu, ni kwamba wakati kupita katika integer, C ni kwenda tu kufanya nakala ya kwamba integer na kupita kwa kazi. awali variable haitabadilika mara moja kazi ni kumaliza. Na safu, kwa upande mwingine, ni si kwenda kufanya nakala, na wewe utakuwa kweli kuwa editing sana safu yenyewe. 

Hivyo aina moja ya aina ni uteuzi aina. aina uteuzi kazi kwa kuanzia saa mwanzo, na kisha iterate juu ya kupata na hiki ndogo. Na kisha kubadilishana kwamba ndogo hiki kwa moja kwanza. Na kisha hoja ya hiki pili , Kupata ijayo ndogo hiki, na kisha kubadilishana kwamba pamoja na hiki pili katika safu kwa sababu hiki kwanza tayari yamepangwa. Na hivyo basi kuendelea kwa kila hiki katika kutambua ndogo thamani na swapping nje. 

Kwa maana Mimi ni sawa na 0, hiki kwanza sana kwa n minus 1, wewe ni kwenda kulinganisha kila thamani ya pili baada ya kuwa na kupata index ya thamani ya chini. Mara baada ya kupata thamani ya chini index, unaweza kubadilishana kwamba thamani ya safu kiwango cha chini na safu I. 

Aina nyingine ya aina hiyo unaweza kutekeleza ni Bubble aina. Hivyo Bubble aina iterates juu ya orodha kulinganisha mambo karibu na swapping mambo ambayo ni ili sahihi. Na kwa njia hii, hiki kubwa mapenzi Bubble hadi mwisho. Na orodha ni vyema mara moja hakuna zaidi mambo wamekuwa walibadilishana. 

Hivyo wale ni mifano miwili ya aina algorithms kwamba unaweza kutekeleza kwa kupata mpango. Mara baada ya kumaliza aina, na wameweza kufanyika search, wewe ni kumaliza. Jina langu ni Zamyla, na hii ni CS50. 

[Music kucheza]