1 00:00:00,000 --> 00:00:08,532 >> [Predvaja glasba] 2 00:00:08,532 --> 00:00:12,060 >> ZAMYLA CHAN: Prva stvar, ki jo morda obvestilo o najdbi je, da smo že 3 00:00:12,060 --> 00:00:13,450 so zapisana koda za nas. 4 00:00:13,450 --> 00:00:15,160 To se imenuje porazdelitev koda. 5 00:00:15,160 --> 00:00:18,000 Torej ne samo pisanje lastnega kodo iz nič več. 6 00:00:18,000 --> 00:00:22,800 Namesto tega smo zapolnjevanje praznin v nekaterih obstoječo kodo. 7 00:00:22,800 --> 00:00:27,790 >> Program find.c vpraša po številkah zapolniti senu, išče 8 00:00:27,790 --> 00:00:32,189 senu uporabniško predložiti iglo, in to počne tako, da kliče vrste in 9 00:00:32,189 --> 00:00:35,590 iskanja, funkcije so opredeljena V helpers.c. 10 00:00:35,590 --> 00:00:37,670 Torej je find.c napisal že. 11 00:00:37,670 --> 00:00:40,770 Vaša naloga je, da napišete pomočnice. 12 00:00:40,770 --> 00:00:41,870 >> Torej, kaj počnemo? 13 00:00:41,870 --> 00:00:44,210 Mi smo za izvajanje dveh funkcij. 14 00:00:44,210 --> 00:00:49,030 Iskanje, ki vrne true, če vrednost se nahaja v senu, vračanje 15 00:00:49,030 --> 00:00:51,370 false, če je vrednost ne v senu. 16 00:00:51,370 --> 00:00:57,990 In potem smo tudi izvajanje vrste ki sortira array imenovano vrednosti. 17 00:00:57,990 --> 00:00:59,960 >> Torej, kaj je dosti iskanje. 18 00:00:59,960 --> 00:01:04,560 Iskanje je trenutno izvaja kot linearno iskanje, vendar lahko veliko naredijo 19 00:01:04,560 --> 00:01:05,550 boljši od tega. 20 00:01:05,550 --> 00:01:09,910 Linearni iskanje se izvaja v O časa, N, pri čemer je zelo počasno. 21 00:01:09,910 --> 00:01:13,850 Čeprav lahko iskanje na katerem koli seznamu dati na to. 22 00:01:13,850 --> 00:01:20,130 Vaša naloga je, da se izvaja binarno iskanje, ki je teči čas O log n. 23 00:01:20,130 --> 00:01:21,130 To je zelo hitro. 24 00:01:21,130 --> 00:01:23,170 >> Ampak tam je določilo. 25 00:01:23,170 --> 00:01:27,600 Binarno iskanje lahko iščete le skozi predhodno razvrščena-seznamov. 26 00:01:27,600 --> 00:01:30,370 Zakaj je tako? 27 00:01:30,370 --> 00:01:32,620 >> Pa si oglejmo primer. 28 00:01:32,620 --> 00:01:36,280 Glede na niz vrednot, senu, bomo morali iskati 29 00:01:36,280 --> 00:01:37,130 iglo. 30 00:01:37,130 --> 00:01:40,460 In v tem primeru celo tri. 31 00:01:40,460 --> 00:01:44,130 Tako, da binarno iskanje deluje, je, da primerjamo srednjo vrednost 32 00:01:44,130 --> 00:01:48,370 matrika z iglo, podobno kot kako smo odprli imenik na sredino 33 00:01:48,370 --> 00:01:50,660 stran v ničelni teden. 34 00:01:50,660 --> 00:01:54,650 >> Torej po primerjavi srednji vrednosti igle, lahko zavržemo bodisi 35 00:01:54,650 --> 00:01:58,530 levo ali desno polovico matrike s poostritvijo svoje meje. 36 00:01:58,530 --> 00:02:03,390 V tem primeru, ker so tri, naš igle, manj kot 10, srednji vrednosti, 37 00:02:03,390 --> 00:02:05,990 Pravica vezan, lahko zmanjša. 38 00:02:05,990 --> 00:02:08,400 Ampak poskusiti, da bi svoje meje tako strogo, kot je mogoče. 39 00:02:08,400 --> 00:02:11,630 Če je srednja vrednost ni igla, potem veste, da vam ni treba, da 40 00:02:11,630 --> 00:02:13,010 jo vključite v vaše iskanje. 41 00:02:13,010 --> 00:02:17,310 Torej imaš vezan, lahko pritrdite išči meje le majhen košček več, 42 00:02:17,310 --> 00:02:21,770 in tako naprej in tako naprej, dokler ste našli iglo. 43 00:02:21,770 --> 00:02:23,480 >> Torej, kaj psevdokoda izgledal? 44 00:02:23,480 --> 00:02:28,420 No, ko smo še vedno gleda skozi seznam in še vedno elemente 45 00:02:28,420 --> 00:02:33,690 poglej v, vzamemo na sredini seznama, in primerjajte to srednjo vrednost 46 00:02:33,690 --> 00:02:34,950 naša igla. 47 00:02:34,950 --> 00:02:37,310 Če so enaki, potem to pomeni, da ste našel iglo in smo lahko 48 00:02:37,310 --> 00:02:38,990 vrne true. 49 00:02:38,990 --> 00:02:42,870 >> V nasprotnem primeru, če je igla manj kot srednja vrednost, potem to pomeni, da 50 00:02:42,870 --> 00:02:47,280 lahko zavržemo desno polovico, in samo iskanje po levi strani matrike. 51 00:02:47,280 --> 00:02:51,090 V nasprotnem primeru bomo iskanje desni strani polja. 52 00:02:51,090 --> 00:02:54,410 In na koncu, če ne boste imeli več elementov pustili za iskanje pa vam 53 00:02:54,410 --> 00:02:58,050 niso našli svojo iglo še ni, potem si vrne false ker igla 54 00:02:58,050 --> 00:03:01,890 zagotovo ni v senu. 55 00:03:01,890 --> 00:03:05,270 >> Sedaj lepo stvar o tem psevdokoda v binarnem iskanju je, da se lahko 56 00:03:05,270 --> 00:03:09,940 razlagati tako, da bodisi ponavljajoč ali rekurzivna izvajanje. 57 00:03:09,940 --> 00:03:13,810 Tako da bi bilo rekurzivni, če se imenuje Iskalna funkcija v iskanju 58 00:03:13,810 --> 00:03:17,350 deluje na obeh polovici matrike. 59 00:03:17,350 --> 00:03:21,030 Pokrili bomo rekurzijo malce kasneje v Seveda, vendar ne vedo, da je 60 00:03:21,030 --> 00:03:24,190 možnost, če želite poskusiti. 61 00:03:24,190 --> 00:03:26,030 >> Zdaj pa si oglejmo vrste. 62 00:03:26,030 --> 00:03:30,750 Razvrsti traja vrsto in celo N, pri čemer je velikost polja. 63 00:03:30,750 --> 00:03:34,030 Sedaj obstaja več različnih vrst z menoj, in si lahko ogledate nekaj 64 00:03:34,030 --> 00:03:36,370 kratke hlače za predstavitve in obrazložitve. 65 00:03:36,370 --> 00:03:39,580 Vrsta donos za naše Funkcija razvrščanja je nična. 66 00:03:39,580 --> 00:03:43,580 To pomeni, da ne bomo za vrnitev vsakega paleto od vrste. 67 00:03:43,580 --> 00:03:48,140 Mi smo dejansko dogaja, da zelo spremenila matrika, ki je bil sprejet v nas. 68 00:03:48,140 --> 00:03:52,290 >> In da je to mogoče zato, ker so nizi s sklicevanjem na C. minilo Zdaj bomo 69 00:03:52,290 --> 00:03:55,290 glej več o tem kasneje, ampak Bistvena razlika med minevanja 70 00:03:55,290 --> 00:03:59,340 nekaj podobnega celo število in prenosu v matriki, je, da ko 71 00:03:59,340 --> 00:04:03,490 prenesti v celo število, C je le, da bo naredite kopijo tega celo število in mimo 72 00:04:03,490 --> 00:04:04,450 je za funkcijo. 73 00:04:04,450 --> 00:04:08,530 Prvotni spremenljivka se ne bo spremenila ko je funkcija končana. 74 00:04:08,530 --> 00:04:12,480 S paleto, na drugi strani pa gre ne dogaja, da bi kopijo, in boste 75 00:04:12,480 --> 00:04:17,910 dejansko urejanje zelo matrika sama. 76 00:04:17,910 --> 00:04:21,269 >> Torej en tip vrste je Izbor sort. 77 00:04:21,269 --> 00:04:24,750 Izbor sortiranje deluje s pričetkom pri začetek, nato pa ponovitev 78 00:04:24,750 --> 00:04:26,820 znova in poiskati najmanjši element. 79 00:04:26,820 --> 00:04:30,710 In potem ste zamenjali da najmanjša element s prvo. 80 00:04:30,710 --> 00:04:34,360 In potem premaknete na drugi element , Našli naslednji najmanjši 81 00:04:34,360 --> 00:04:38,320 element, in nato zamenjali da z Drugi element v matriki, ker 82 00:04:38,320 --> 00:04:41,100 Prvi element je že razporejene. 83 00:04:41,100 --> 00:04:45,370 In tako potem naprej za vsak element pri ugotavljanju najmanjše 84 00:04:45,370 --> 00:04:47,690 vrednost in zamenjavo ven. 85 00:04:47,690 --> 00:04:53,460 >> Kajti enaka 0, zelo prvi element do n minus 1, boste za primerjavo 86 00:04:53,460 --> 00:04:57,820 vsaka naslednja vrednost, po tem in najti Indeks najmanjšo vrednost. 87 00:04:57,820 --> 00:05:02,520 Ko boste našli indeks najnižja vrednost, lahko swap, da je vrednost matrike 88 00:05:02,520 --> 00:05:05,930 Najmanjši in matrika I. 89 00:05:05,930 --> 00:05:09,760 >> Druga vrsta vrste, ki jih lahko izvajati je bubble sort. 90 00:05:09,760 --> 00:05:14,380 Torej bubble vrsta ponovi več na seznamu primerjavo sosednje elemente in 91 00:05:14,380 --> 00:05:17,720 zamenjavo elemente, ki so v napačnem vrstnem redu. 92 00:05:17,720 --> 00:05:22,380 In na ta način, največji del bo mehurček do konca. 93 00:05:22,380 --> 00:05:28,070 In seznam razporejene enkrat več Elementi so bile zamenjane. 94 00:05:28,070 --> 00:05:31,920 >> Torej, to sta dva primera neke algoritmi, ki jih lahko izvajajo za 95 00:05:31,920 --> 00:05:33,230 Program najdba. 96 00:05:33,230 --> 00:05:37,350 Ko končate urejanje, in ste storjeno iskanje, ste končali. 97 00:05:37,350 --> 00:05:39,720 Ime je Zamyla, in to je CS50. 98 00:05:39,720 --> 00:05:46,987 >> [Predvaja glasba]