1 00:00:00,000 --> 00:00:06,370 2 00:00:06,370 --> 00:00:08,150 >> JASON HIRSCHHORN: Welcome til uge tre, alle sammen. 3 00:00:08,150 --> 00:00:11,650 Vi har en travl men spændende sektion foran os. 4 00:00:11,650 --> 00:00:17,010 Så det første, fordi vi har gjort nogle fremskridt med kurset, men vi har stadig 5 00:00:17,010 --> 00:00:20,570 har en masse at lære tilbage at gøre, er jeg kommer til at vise jer nogle ressourcer 6 00:00:20,570 --> 00:00:24,160 der skulle vise sig at være utrolig nyttigt, da du ikke kun nærmer dig din 7 00:00:24,160 --> 00:00:28,130 Problemet sætter, men også fordøje alle det materiale, vi giver jer i 8 00:00:28,130 --> 00:00:30,800 foredrag og shorts og afsnit. 9 00:00:30,800 --> 00:00:34,790 >> Så vi kommer til at tilbringe de første 20 til 25 minutters afsnit går over 10 00:00:34,790 --> 00:00:38,630 GDB, som du måske eller måske ikke har anvendes på dette tidspunkt, men det er en 11 00:00:38,630 --> 00:00:42,570 utroligt nyttigt værktøj, der vil hjælpe dig debug dine programmer. 12 00:00:42,570 --> 00:00:46,060 En masse af jer måske har brugt printf i midten af ​​dit program til at regne 13 00:00:46,060 --> 00:00:47,430 ud af, hvad en variabel umådeholdent. 14 00:00:47,430 --> 00:00:52,060 GDB er endnu bedre end printf og ikke skrue op din kode, fordi du 15 00:00:52,060 --> 00:00:53,320 køre det på en eksekverbar fil. 16 00:00:53,320 --> 00:00:56,500 Så vi vil gå over de 10 mest nyttige kommandoer, du har brug for GDB, og vi er 17 00:00:56,500 --> 00:01:00,540 kommer til at gå på en øvelse sammen, så i problemet sæt tre og videre, du 18 00:01:00,540 --> 00:01:03,320 kan bruge GDB at hjælpe debug dine programmer. 19 00:01:03,320 --> 00:01:06,420 Og endelig, vi kommer til at gå over nogle sortering og søgning algoritmer 20 00:01:06,420 --> 00:01:10,590 at du så i foredrag, og vi er vil faktisk kode, ikke blot 21 00:01:10,590 --> 00:01:17,360 pseudokode, men kode binær søgning, boble sortere, og udvælgelse slags. 22 00:01:17,360 --> 00:01:20,090 >> Så det første, jeg ønsker at gå over ressourcerne. 23 00:01:20,090 --> 00:01:23,530 Dette er en omfattende liste, og det er mindre skrift, fordi jeg havde en masse at 24 00:01:23,530 --> 00:01:24,390 passe på her. 25 00:01:24,390 --> 00:01:26,950 Men disse vil ikke kun hjælpe dig, igen, med problemet sæt og 26 00:01:26,950 --> 00:01:30,760 fordøje de oplysninger, du har lært, men afgjort, kom quiz tid, vil disse 27 00:01:30,760 --> 00:01:32,130 være utrolig nyttigt. 28 00:01:32,130 --> 00:01:34,700 Så det første, foredraget noter. 29 00:01:34,700 --> 00:01:39,480 Hvis du går til cs50.net/lectures og rulle til den pågældende uge og dag, 30 00:01:39,480 --> 00:01:43,120 vil du se at der er bemærkninger til de enkelte foredrag, der er ikke blot en 31 00:01:43,120 --> 00:01:47,250 transkript, men en redigeret version af hvad der blev dækket i foredrag med kode 32 00:01:47,250 --> 00:01:49,610 snippets og andre nyttige godbidder. 33 00:01:49,610 --> 00:01:52,220 Jeg kan varmt anbefale at gå over dem. 34 00:01:52,220 --> 00:01:55,340 Og så så godt, er der kildekode tilgængelig fra hver forelæsning. 35 00:01:55,340 --> 00:02:00,050 Og igen, vil disse dias også være tilgængelig online på cs50.net/sections 36 00:02:00,050 --> 00:02:01,480 denne aften. 37 00:02:01,480 --> 00:02:06,860 >> Så sekund er de shorts hver uge, dækker emner, som regel 5 til 15 38 00:02:06,860 --> 00:02:08,090 minutter i længden. 39 00:02:08,090 --> 00:02:12,310 Og dem, forhåbentlig vil give dig en stor primer på forskellige emner. 40 00:02:12,310 --> 00:02:12,870 Tredje - 41 00:02:12,870 --> 00:02:16,370 og det er helt nyt denne år - er study.cs50.net. 42 00:02:16,370 --> 00:02:20,110 Hvis du ikke har tjekket det ud, jeg varmt anbefale, at du gør det. 43 00:02:20,110 --> 00:02:21,100 Du kommer til at vælge et emne. 44 00:02:21,100 --> 00:02:23,040 Vi har dusinvis af emner på der. 45 00:02:23,040 --> 00:02:24,770 Så du for eksempel vælge Funktioner. 46 00:02:24,770 --> 00:02:27,270 Det giver dig nogle dias og noter om funktioner. 47 00:02:27,270 --> 00:02:31,190 Det er faktisk de dias, TFs opfordres til at bruge under vores 48 00:02:31,190 --> 00:02:32,710 præsentationer i afsnit. 49 00:02:32,710 --> 00:02:35,040 Der er også tips og tricks til at håndtere med funktioner, og der er 50 00:02:35,040 --> 00:02:37,290 praksis problemer, der hjælper du arbejder med funktioner. 51 00:02:37,290 --> 00:02:41,500 Vi giver dig også links til kort på funktioner og de tidspunkter, der fungerer 52 00:02:41,500 --> 00:02:42,750 er kommet op i foredraget. 53 00:02:42,750 --> 00:02:46,550 Så study.cs50.net Nybygget dette år, en fantastisk ressource. 54 00:02:46,550 --> 00:02:52,180 >> Dernæst har jeg mand, som er den manuelle kommando, som du kan køre på 55 00:02:52,180 --> 00:02:52,770 kommandolinjen. 56 00:02:52,770 --> 00:02:57,880 Så hvis du har spørgsmål om en kommando for eksempel rand, som vi 57 00:02:57,880 --> 00:03:00,900 stødte i sidste uge under sektion og du har sandsynligvis stødt på 58 00:03:00,900 --> 00:03:05,380 dit problem sæt, når der går gennem generere kode, men hvis du skriver mand 59 00:03:05,380 --> 00:03:09,980 rand, får du den side, fortæller dig alt om rand. 60 00:03:09,980 --> 00:03:14,040 Det giver dig, hvad det tager, det parametre, det tager, samt afkast 61 00:03:14,040 --> 00:03:16,530 type og en kort beskrivelse af denne funktion. 62 00:03:16,530 --> 00:03:17,500 >> Så tjek rand. 63 00:03:17,500 --> 00:03:22,270 Det kan være lidt ordrige og forvirrende, så nogle gange finder jeg, at 64 00:03:22,270 --> 00:03:26,150 simpelthen at google, hvad jeg ønsker at vide er den bedste måde at finde svaret. 65 00:03:26,150 --> 00:03:27,940 Så praksis med Google. 66 00:03:27,940 --> 00:03:28,600 Få gode hos Google. 67 00:03:28,600 --> 00:03:30,600 Det vil blive din bedste ven. 68 00:03:30,600 --> 00:03:34,300 >> Samt Google, hvis du ikke kan finde det på Google, cs50.net/discuss, det er 69 00:03:34,300 --> 00:03:35,550 diskussionsforum. 70 00:03:35,550 --> 00:03:39,390 Chancerne er, hvis du har et spørgsmål, en dine 700 + peers har også at 71 00:03:39,390 --> 00:03:42,110 spørgsmål og kan have bedt allerede i diskutere 72 00:03:42,110 --> 00:03:43,540 fora og har det besvaret. 73 00:03:43,540 --> 00:03:48,130 Så hvis du har et almindeligt spørgsmål eller du har et spørgsmål som du mener 74 00:03:48,130 --> 00:03:52,300 måske andre mennesker måske har kørt ind, tjek cs50.net/discuss. 75 00:03:52,300 --> 00:03:55,450 >> Endelig er den sidste to, hvis du vil tale med en virkelig menneske, kontor 76 00:03:55,450 --> 00:03:57,770 timer mandag til fredag. 77 00:03:57,770 --> 00:04:00,850 Der er også online kontortid for udvidelse studerende. 78 00:04:00,850 --> 00:04:04,370 Og sidst men bestemt ikke mindst, mig, udråbstegn. 79 00:04:04,370 --> 00:04:05,960 Du har alle mine kontaktoplysninger. 80 00:04:05,960 --> 00:04:11,940 Hvis du har brug for noget, bedes du aldrig velkommen til at kontakte mig. 81 00:04:11,940 --> 00:04:14,020 Altid velkommen til at gøre det. 82 00:04:14,020 --> 00:04:17,490 Meget få af jer har tilføjet mig på Gchat, så der har været skuffende, 83 00:04:17,490 --> 00:04:20,410 men forhåbentlig, der vil skifte mellem dette og næste afsnit. 84 00:04:20,410 --> 00:04:22,105 Eventuelle spørgsmål, så langt på ressourcerne? 85 00:04:22,105 --> 00:04:25,670 86 00:04:25,670 --> 00:04:27,450 Store. 87 00:04:27,450 --> 00:04:34,280 >> Endelig et andet stik til feedback, sayat.me/cs50. 88 00:04:34,280 --> 00:04:37,050 Du kan give mig anonym tilbagemelding om, hvordan jeg gør. 89 00:04:37,050 --> 00:04:38,320 Det var virkelig nyttige i sidste uge. 90 00:04:38,320 --> 00:04:41,890 Jeg fik et par kommentarer fra jer lige efter sektion, plus fra 91 00:04:41,890 --> 00:04:44,750 andre studerende, der så det i løbet af ugen, og det 92 00:04:44,750 --> 00:04:46,830 var utroligt hjælpsomme. 93 00:04:46,830 --> 00:04:50,250 Jeg vil forsøge at begrænse min brug af ordet "sød", men jeg vil vise min 94 00:04:50,250 --> 00:04:52,410 entusiasme og begejstring på andre måder. 95 00:04:52,410 --> 00:04:56,550 Men der var andre yderligere materielle feedbacks, 96 00:04:56,550 --> 00:04:57,600 både plusser og Delta. 97 00:04:57,600 --> 00:05:00,480 Så please, jeg giver jer tilbagemeldinger på dit problem sæt. 98 00:05:00,480 --> 00:05:01,790 Du er velkommen til at give mig feedback på min undervisning. 99 00:05:01,790 --> 00:05:04,010 Jeg er her for jer. 100 00:05:04,010 --> 00:05:05,270 >> Store. 101 00:05:05,270 --> 00:05:07,020 Det er alt jeg har for den første sektion. 102 00:05:07,020 --> 00:05:08,565 Er der nogen har nogen spørgsmål indtil videre? 103 00:05:08,565 --> 00:05:12,370 104 00:05:12,370 --> 00:05:14,640 Og jeg har en note til vagtcentralen. 105 00:05:14,640 --> 00:05:21,200 Extension studerende har messaged mig siger, at de får ikke nogen lyd, 106 00:05:21,200 --> 00:05:23,870 men der er ude af min magt at fastsætte. 107 00:05:23,870 --> 00:05:25,280 Så forhåbentlig, der får løst inden længe. 108 00:05:25,280 --> 00:05:28,850 Hvis du ser online, hej, men du kan ikke høre mig. 109 00:05:28,850 --> 00:05:33,860 >> Så først skal vi at gå gennem GDB. 110 00:05:33,860 --> 00:05:37,100 GDB, som jeg antydede tidligere, er et fejlfindingsværktøj 111 00:05:37,100 --> 00:05:39,040 meget bedre end printf. 112 00:05:39,040 --> 00:05:44,700 Så for at komme i gang med GDB, gutter, hvis du ønsker at åbne op dit apparat 113 00:05:44,700 --> 00:05:49,070 og tage den fil, jeg sendt til dig tidligere - denne fil vil også være 114 00:05:49,070 --> 00:05:51,940 tilgængelig online i en bit - 115 00:05:51,940 --> 00:05:55,700 og køre GDB. / navnet på filen. 116 00:05:55,700 --> 00:05:58,580 Først, selvfølgelig, er du nødt til at kompilere fil fordi GDB fungerer kun på 117 00:05:58,580 --> 00:05:59,890 eksekverbare filer. 118 00:05:59,890 --> 00:06:02,300 >> Men hvis du nogensinde ønsker at starte GDB, den første ting du gør, 119 00:06:02,300 --> 00:06:04,550 du kører GDB. / Cæsar. 120 00:06:04,550 --> 00:06:08,340 Så det er navnet på det program, vi er kommer til at gå med det lige nu. 121 00:06:08,340 --> 00:06:12,810 Så jeg har tænkt mig at skrive gøre Cæsar, som vil give mig en eksekverbar fil 122 00:06:12,810 --> 00:06:14,100 her markeret med grønt. 123 00:06:14,100 --> 00:06:19,250 Og så har jeg tænkt mig at køre GDB. / Cesar. 124 00:06:19,250 --> 00:06:19,810 >> Og der du går. 125 00:06:19,810 --> 00:06:24,540 Du kan se vi har noget tekst fortæller mig om den version af GDB, giver mig 126 00:06:24,540 --> 00:06:27,570 nogle oplysninger om garanti, og så vi har BNP prompt, som ser slags 127 00:06:27,570 --> 00:06:29,350 ligesom vores kommandolinje prompt, men du kan se det er åbent 128 00:06:29,350 --> 00:06:32,510 paren, GDB, tæt paren. 129 00:06:32,510 --> 00:06:36,520 Før vi fortsætter, og debug denne fil som jeg sendte til jer alle, lad os se på 130 00:06:36,520 --> 00:06:40,220 nogle nyttige kommandoer, så vi har en fornemmelse af det, vi kommer til at dække. 131 00:06:40,220 --> 00:06:45,060 >> Disse kommandoer er vist her i rækkefølge, som jeg normalt bruger dem. 132 00:06:45,060 --> 00:06:50,230 Så jeg starter mit program ved at køre GBD. / Navnet på det program, 133 00:06:50,230 --> 00:06:51,360 i dette tilfælde, Cæsar. 134 00:06:51,360 --> 00:06:57,430 Og så den første ting jeg gør 99,9% af tiden er typen pause betyder. 135 00:06:57,430 --> 00:06:59,070 Det sætter en pause punkt på main. 136 00:06:59,070 --> 00:07:03,260 Væsentlige, hvad du laver der er programmet vil stoppe ved 137 00:07:03,260 --> 00:07:06,100 vigtigste, så du kan begynde at undersøge det linie linje, snarere end at køre alle 138 00:07:06,100 --> 00:07:07,040 vejen igennem. 139 00:07:07,040 --> 00:07:09,730 Du kan bryde på forskellige din kode, men vigtigste er generelt en 140 00:07:09,730 --> 00:07:11,870 godt sted at starte. 141 00:07:11,870 --> 00:07:14,840 >> Den næste kommando jeg kører køres. 142 00:07:14,840 --> 00:07:17,400 Det starter programmet kører, og hvis du har brug for at indtaste kommandolinjen 143 00:07:17,400 --> 00:07:19,090 argumenter, du kører det på den kommando. 144 00:07:19,090 --> 00:07:20,500 Løb med argumenterne. 145 00:07:20,500 --> 00:07:25,000 Så da vi skal over en version af C, som er det program, du fyre 146 00:07:25,000 --> 00:07:26,160 skrev for PSET to - 147 00:07:26,160 --> 00:07:29,880 denne ene, selvfølgelig, har nogle bugs i det, som forhåbentlig finder vi - 148 00:07:29,880 --> 00:07:32,810 vi kommer til at køre løb med en kommando line argumenter fordi Cæsar, 149 00:07:32,810 --> 00:07:34,860 som du fyre vide per problemet sæt spec, tager nogle 150 00:07:34,860 --> 00:07:36,380 kommandolinjeargumenter. 151 00:07:36,380 --> 00:07:40,000 >> De næste par kommandoer, den næste man faktisk kaldes næste. 152 00:07:40,000 --> 00:07:42,470 At man tager dig linje for linje gennem dit program. 153 00:07:42,470 --> 00:07:45,800 Så rammer n derefter på Enter tager dig til næste linje, udførelse 154 00:07:45,800 --> 00:07:46,880 den foregående linje. 155 00:07:46,880 --> 00:07:49,440 Step tager du ikke kun til den næste linje, men det 156 00:07:49,440 --> 00:07:51,070 tager dig inde funktioner. 157 00:07:51,070 --> 00:07:54,310 Så hvis du har skrevet en funktion i din kode, eller hvis du ønsker at udforske en 158 00:07:54,310 --> 00:07:57,820 til i, for eksempel, kan du hit s, og snarere end at gå til den næste linje 159 00:07:57,820 --> 00:08:02,390 den fil, du går igennem lige nu, vil du faktisk træde ind 160 00:08:02,390 --> 00:08:04,670 denne funktion, og se sin kode. 161 00:08:04,670 --> 00:08:12,300 >> Listen viser dig, i meget brugervenlig format, de 10 eller deromkring linjer omkring 162 00:08:12,300 --> 00:08:14,940 hvor du i øjeblikket er i din kode så du kan faktisk se filen 163 00:08:14,940 --> 00:08:17,810 snarere end at skulle skifte tilbage og tilbage mellem forskellige synspunkter. 164 00:08:17,810 --> 00:08:21,890 Print er ligesom printf, som navnet antyder. 165 00:08:21,890 --> 00:08:24,020 Det viser dig, hvad en variabel lig. 166 00:08:24,020 --> 00:08:25,870 >> Info lokale er virkelig nyttige. 167 00:08:25,870 --> 00:08:27,740 Dette er en særlig udgave af print. 168 00:08:27,740 --> 00:08:31,770 Info lokale viser dig alle de lokale variabler, udskriver dem alle ud for dig 169 00:08:31,770 --> 00:08:33,380 der findes i øjeblikket. 170 00:08:33,380 --> 00:08:36,360 Så jeg generelt, snarere end at skulle udskrive de fire variable, som jeg er 171 00:08:36,360 --> 00:08:39,929 nysgerrig, hvis jeg er i en for-løkke, for eksempel, jeg bare skrive info lokalbefolkningen, 172 00:08:39,929 --> 00:08:43,470 og det vil vise mig, hvad min counter i lig, samt array, at jeg er 173 00:08:43,470 --> 00:08:45,130 arbejder på ligemænd. 174 00:08:45,130 --> 00:08:47,530 >> Endelig fortsætter. 175 00:08:47,530 --> 00:08:49,300 Typing pause stopper dig ved knækpunkt. 176 00:08:49,300 --> 00:08:51,380 Du kan gå igennem linje linje med næste og trin. 177 00:08:51,380 --> 00:08:55,640 Fortsæt kører programmet til din næste knækpunkt eller indtil afslutningen, hvis 178 00:08:55,640 --> 00:08:57,180 der ikke er flere break point. 179 00:08:57,180 --> 00:09:00,060 Disable fjerner break point, hvis du besluttede pause på vigtigste var 180 00:09:00,060 --> 00:09:01,890 upassende, du ønsker at sætte den et andet sted. 181 00:09:01,890 --> 00:09:05,090 Og endelig q, holde op, får ud af GDB. 182 00:09:05,090 --> 00:09:10,784 >> Så dette program,. / Cæsar, vi at se igennem lige nu, og vi 183 00:09:10,784 --> 00:09:13,490 vil bruge GDB at finde bugs i dette program. 184 00:09:13,490 --> 00:09:18,110 Jeg kørte dette program tidligere med Check 50, og jeg fik en panderynken. 185 00:09:18,110 --> 00:09:22,310 Alt det eksisterede, er det kompileret, det bestået en masse af prøverne, men for 186 00:09:22,310 --> 00:09:27,950 eller anden grund, var det ikke passere den femte test, drejning BARFOO alle caps, i 187 00:09:27,950 --> 00:09:33,350 E-D-U-I-R-R, alle kasketter, bruge tre som en nøgle. 188 00:09:33,350 --> 00:09:34,090 Jeg fik temmelig tæt på. 189 00:09:34,090 --> 00:09:35,410 Jeg slap med et bogstav. 190 00:09:35,410 --> 00:09:37,340 Så der er nogle små fejl i her. 191 00:09:37,340 --> 00:09:38,070 Jeg har kigget igennem min kode. 192 00:09:38,070 --> 00:09:38,850 Jeg kunne ikke regne det ud. 193 00:09:38,850 --> 00:09:41,740 Forhåbentlig kan du fyre hjælpe mig regne ud, hvad denne fejl er. 194 00:09:41,740 --> 00:09:44,610 >> Så det er den fejl, vi er søger efter. 195 00:09:44,610 --> 00:09:46,090 Lad os flytte ind GDB. 196 00:09:46,090 --> 00:09:51,100 Igen, jeg har kørt GDB. / Cæsar, så nu er vi i GDB. 197 00:09:51,100 --> 00:09:54,290 Og hvad er den første ting jeg skal gøre? 198 00:09:54,290 --> 00:09:56,680 Jeg har netop indgået GDB. 199 00:09:56,680 --> 00:10:00,316 Nogen give mig en god kommando til at komme ind. 200 00:10:00,316 --> 00:10:01,140 >> STUDENT: Break main. 201 00:10:01,140 --> 00:10:01,800 >> JASON HIRSCHHORN: Break main. 202 00:10:01,800 --> 00:10:02,900 Fantastic. 203 00:10:02,900 --> 00:10:03,560 Lad os skrive det i. 204 00:10:03,560 --> 00:10:06,390 Du fyre kan se op her, eller følg sammen på dine computere. 205 00:10:06,390 --> 00:10:09,410 Break vigtigste, og du vil se en break point blev sat til - 206 00:10:09,410 --> 00:10:12,340 det giver mig nogle underlige hukommelse adresse, og det giver mig også den linje nummer. 207 00:10:12,340 --> 00:10:15,310 Hvis jeg skulle se tilbage på denne fil, Jeg ville indse, at main 208 00:10:15,310 --> 00:10:17,700 skete på linie 21. 209 00:10:17,700 --> 00:10:18,950 Hvad skal jeg køre næste? 210 00:10:18,950 --> 00:10:22,970 211 00:10:22,970 --> 00:10:25,060 Er mit program kører? 212 00:10:25,060 --> 00:10:25,650 Nej. 213 00:10:25,650 --> 00:10:27,175 Så hvad skal jeg køre næste? 214 00:10:27,175 --> 00:10:27,520 >> STUDENT: Kør. 215 00:10:27,520 --> 00:10:28,050 >> JASON HIRSCHHORN: Kør. 216 00:10:28,050 --> 00:10:30,760 Skal jeg bare køre løb, eller skal Jeg tilføje nogle andre ting i? 217 00:10:30,760 --> 00:10:31,960 >> STUDENT: Løb med argumentet. 218 00:10:31,960 --> 00:10:33,320 >> JASON HIRSCHHORN: Løb med kommandoen argumenter. 219 00:10:33,320 --> 00:10:36,420 Og da jeg debugging en meget specifik tilfælde, skal jeg indtaste det 220 00:10:36,420 --> 00:10:37,120 kommandolinje argument. 221 00:10:37,120 --> 00:10:42,290 Så jeg vil løber tre, der er, igen, output jeg fik fra Check 50. 222 00:10:42,290 --> 00:10:44,240 Start program. 223 00:10:44,240 --> 00:10:45,420 Vi går gennem et par linjer. 224 00:10:45,420 --> 00:10:47,700 Du vil nu se, at vi er på linie 21. 225 00:10:47,700 --> 00:10:49,200 Hvordan kan jeg vide, at vi er på linje 21? 226 00:10:49,200 --> 00:10:52,170 Fordi hvis man ser til venstre af min terminal vindue, der 227 00:10:52,170 --> 00:10:53,120 det siger linie 21. 228 00:10:53,120 --> 00:10:57,010 Og det giver mig, faktisk, det kode, der er på linie 21. 229 00:10:57,010 --> 00:10:58,440 Så jeg misspoke tidligere. 230 00:10:58,440 --> 00:10:59,770 Main er faktisk ikke på linie 21. 231 00:10:59,770 --> 00:11:02,000 Main er et par linjer over 21.. 232 00:11:02,000 --> 00:11:04,300 Men på linje 21, der er hvor vi bryder. 233 00:11:04,300 --> 00:11:06,280 Denne linje kode har endnu ikke udført. 234 00:11:06,280 --> 00:11:06,890 Det er vigtigt. 235 00:11:06,890 --> 00:11:09,120 Den linje, du ser ikke har blevet henrettet endnu. 236 00:11:09,120 --> 00:11:12,650 Det er den næste linje kode du er ved at udføre. 237 00:11:12,650 --> 00:11:15,860 >> Så den næste linje, som du fyre er sikkert bekendt med, er dette 238 00:11:15,860 --> 00:11:20,070 tilstand kontrol for at se, om jeg har indtastet en kommandolinje argument. 239 00:11:20,070 --> 00:11:22,140 Og et til i, hvad der er den anden en del af, at gøre? 240 00:11:22,140 --> 00:11:23,457 Hvad er en til i? 241 00:11:23,457 --> 00:11:24,950 >> STUDENT: at ændre det til et heltal. 242 00:11:24,950 --> 00:11:25,450 >> JASON HIRSCHHORN: Undskyld? 243 00:11:25,450 --> 00:11:27,400 >> STUDENT: Det ændrer den argument til et heltal. 244 00:11:27,400 --> 00:11:30,890 >> JASON HIRSCHHORN: Så en til i skifter arg v1 fra en streng til et heltal. 245 00:11:30,890 --> 00:11:32,140 Og hvad er det kontrol? 246 00:11:32,140 --> 00:11:35,414 247 00:11:35,414 --> 00:11:37,112 >> STUDENT: Hvis der er en anden kommandolinjeargument, bortset 248 00:11:37,112 --> 00:11:38,100 fra at køre programmet. 249 00:11:38,100 --> 00:11:39,460 >> JASON HIRSCHHORN: Og hvad er i anden halvdel af dette 250 00:11:39,460 --> 00:11:41,220 Boolsk udtryk kontrol? 251 00:11:41,220 --> 00:11:42,540 Denne del herovre, en for jeg? 252 00:11:42,540 --> 00:11:44,080 >> STUDENT: Hvis det er negativt. 253 00:11:44,080 --> 00:11:45,380 >> JASON HIRSCHHORN: Making sikker på hvad? 254 00:11:45,380 --> 00:11:47,120 >> STUDENT: At sikre det er i virkeligheden positivt. 255 00:11:47,120 --> 00:11:47,650 >> JASON HIRSCHHORN: Præcis. 256 00:11:47,650 --> 00:11:50,600 Dette er kontrol for at se, om det er negativ, og hvis den er negativ, jeg 257 00:11:50,600 --> 00:11:53,220 har en fornemmelse af den næste linje magt være mig råben på brugeren. 258 00:11:53,220 --> 00:11:55,930 Så lad os ramte ende at udføre denne linje. 259 00:11:55,930 --> 00:11:59,925 Vi kan ikke se, at linje, som du fyre måske forventet at se råben på 260 00:11:59,925 --> 00:12:03,030 bruger og derefter vender tilbage, fordi denne linje ikke udføre. 261 00:12:03,030 --> 00:12:03,840 Jeg trådte 3. 262 00:12:03,840 --> 00:12:06,860 Så jeg havde faktisk indtaste to kommando line argumenter, og 3 er 263 00:12:06,860 --> 00:12:07,610 større end nul. 264 00:12:07,610 --> 00:12:09,950 Så vi så, at linje, vi henrettet, men vi havde ikke træde 265 00:12:09,950 --> 00:12:11,300 inde i hvis betingelse. 266 00:12:11,300 --> 00:12:17,060 >> Så nu, næste, jeg ser jeg indstilling int nøgle svarer til en til i arg v1. 267 00:12:17,060 --> 00:12:18,840 Så det er mig skabe en variabel nøgle. 268 00:12:18,840 --> 00:12:22,450 Så hvis jeg udskrive nøgle lige nu, fordi der giver dig mulighed for at se den 269 00:12:22,450 --> 00:12:26,040 værdien inden variablen, nøgle er lig 47.. 270 00:12:26,040 --> 00:12:28,810 Det er underligt, men selvfølgelig, det er fordi jeg ikke har 271 00:12:28,810 --> 00:12:30,490 henrettet denne linje endnu. 272 00:12:30,490 --> 00:12:35,880 Så nu, hvis jeg ramte n, udføre denne linje, og gøre print nøgle, vil nøgle lig 3, 273 00:12:35,880 --> 00:12:37,740 hvilket er, hvad vi forventer, at lig. 274 00:12:37,740 --> 00:12:41,170 >> Så igen i GDB, den linje, du se, du ikke har udført endnu. 275 00:12:41,170 --> 00:12:44,850 Du er nødt til at slå n eller s eller et nummer af andre kommandoer til faktisk 276 00:12:44,850 --> 00:12:46,610 udføre den pågældende linje. 277 00:12:46,610 --> 00:12:47,380 Print nøgle. 278 00:12:47,380 --> 00:12:48,280 Keys ved 3. 279 00:12:48,280 --> 00:12:49,750 Så langt, så godt. 280 00:12:49,750 --> 00:12:51,000 String er almindelig tekst. 281 00:12:51,000 --> 00:12:52,270 Lad os udføre denne linje. 282 00:12:52,270 --> 00:12:53,970 Jeg får en snor fra brugeren. 283 00:12:53,970 --> 00:12:58,690 >> Lad os se i min Check 50, jeg indtaste BARFOO alle caps, så 284 00:12:58,690 --> 00:13:01,330 det er, hvad jeg vil komme ind. 285 00:13:01,330 --> 00:13:07,300 Hvis jeg nu udskrive almindelig tekst. 286 00:13:07,300 --> 00:13:08,610 Du vil se det er lig en streng. 287 00:13:08,610 --> 00:13:11,100 Det giver mig nogle andre underlige hexadecimal nummer, men det gør i 288 00:13:11,100 --> 00:13:13,620 Faktisk sige, at min streng er BARFOO. 289 00:13:13,620 --> 00:13:19,308 Hvis jeg ønskede at se, hvad nøglen svarede på dette punkt, hvordan kunne jeg tjekke nøgle? 290 00:13:19,308 --> 00:13:20,710 >> STUDENT: Print nøgle. 291 00:13:20,710 --> 00:13:22,010 >> JASON HIRSCHHORN: Print nøgle, nøjagtigt. 292 00:13:22,010 --> 00:13:23,260 Og faktisk, der er en genvej. 293 00:13:23,260 --> 00:13:25,910 Hvis du bliver træt af at skrive print, du kan bare skrive p. 294 00:13:25,910 --> 00:13:28,340 Så p nøgle gør nøjagtig de samme ting. 295 00:13:28,340 --> 00:13:29,730 Og igen, jeg ser det er lig 3. 296 00:13:29,730 --> 00:13:34,760 >> Hvis jeg ønskede at finde ud af, hvad både nøgle og BARFOO svarede samtidig 297 00:13:34,760 --> 00:13:37,215 men jeg var træt af at skrive hver én ud enkeltvis, I 298 00:13:37,215 --> 00:13:38,590 kunne skrive info lokalbefolkningen. 299 00:13:38,590 --> 00:13:41,170 Det giver mig vigtige ligemænd 3. 300 00:13:41,170 --> 00:13:42,500 Almindelig tekst lig BARFOO. 301 00:13:42,500 --> 00:13:45,265 Det giver mig også disse to underlige ting i toppen, denne variabel i og 302 00:13:45,265 --> 00:13:46,590 denne variabel n.. 303 00:13:46,590 --> 00:13:48,460 >> De er faktisk eksisterende i min hovedprogrammet. 304 00:13:48,460 --> 00:13:51,280 Vi har ikke mødt dem endnu, men som et eksempel, der 305 00:13:51,280 --> 00:13:52,880 eksistere i min for-løkke. 306 00:13:52,880 --> 00:13:55,360 Så lige nu, de lige nogle underlige tal, fordi de ikke har været 307 00:13:55,360 --> 00:13:58,300 initialiseret endnu, men de findes stadig i hukommelsen, så de er bare sat 308 00:13:58,300 --> 00:14:00,220 nogle skrald værdi. 309 00:14:00,220 --> 00:14:02,890 Men vi kan se nøglen i almindelig tekst lige der. 310 00:14:02,890 --> 00:14:06,390 >> Så jeg har tænkt mig at udføre denne linje, linie 34, for-løkken. 311 00:14:06,390 --> 00:14:08,220 Vi kommer til at springe i for loop ved at trykke n. 312 00:14:08,220 --> 00:14:10,050 Og vi er inde i for-løkken. 313 00:14:10,050 --> 00:14:11,360 Vi er på vores første check. 314 00:14:11,360 --> 00:14:14,300 Og igen, bør disse slags kigge velkendt for dig, fordi det var en 315 00:14:14,300 --> 00:14:18,080 Cæsar-program, der blev skrevet, men igen, har en slags bug. 316 00:14:18,080 --> 00:14:21,940 >> Og nu, hvis jeg gør info lokalbefolkningen, fordi jeg er indeni, der for-løkke, vil du se 317 00:14:21,940 --> 00:14:23,900 at jeg er lig med nul, som vi forventer. 318 00:14:23,900 --> 00:14:26,820 Det er, hvad vi satte det til og initialiseres det i for-løkken. 319 00:14:26,820 --> 00:14:27,560 n er lig med 6. 320 00:14:27,560 --> 00:14:30,700 Det giver også mening, fordi vi har sat det til strlen almindelig tekst. 321 00:14:30,700 --> 00:14:34,270 Så jeg kan lide at gøre info locals eller udskrive til variabel ofte for at sikre, at 322 00:14:34,270 --> 00:14:36,370 alt er altid hvad Jeg forventer, at det lige. 323 00:14:36,370 --> 00:14:39,800 I dette tilfælde, er alt hvad jeg forventer, at det lige. 324 00:14:39,800 --> 00:14:41,850 >> Så lad os begynde at bevæge sig gennem dette for løkke. 325 00:14:41,850 --> 00:14:45,715 Den linje jeg er på er linie 36, hvis almindelig Teksten i er større end en og almindelig 326 00:14:45,715 --> 00:14:48,540 Teksten i er mindre end eller lig med z. 327 00:14:48,540 --> 00:14:51,880 Jeg kender mit problem er ikke med min første brev, er det med det andet bogstav. 328 00:14:51,880 --> 00:14:56,290 Hvis vi ser tilbage på Check 50 B går til E fint. 329 00:14:56,290 --> 00:14:59,010 Jeg tager A og lade det som en A, ikke ændrer det til D. Så 330 00:14:59,010 --> 00:15:00,200 noget er galt med det andet bogstav. 331 00:15:00,200 --> 00:15:01,640 Så jeg har tænkt mig at flytte der i en anden. 332 00:15:01,640 --> 00:15:06,030 >> Men hvis jeg havde lyst til at kontrollere, hvad almindelig tekst, jeg svarede i dette særlige 333 00:15:06,030 --> 00:15:07,760 tilfælde, jeg mener, det bør være, hvad? 334 00:15:07,760 --> 00:15:10,980 Hvad skal almindelig tekst jeg lige i dette første runde gennem for-løkken? 335 00:15:10,980 --> 00:15:14,046 336 00:15:14,046 --> 00:15:15,110 >> STUDENT: Zero? 337 00:15:15,110 --> 00:15:16,510 >> JASON HIRSCHHORN: Almindelig tekst af I? 338 00:15:16,510 --> 00:15:21,180 Så det bør være hovedstad B. Jeg, selvfølgelig, lig med nul, men almindelig tekst 339 00:15:21,180 --> 00:15:25,600 beslag nul lukket beslag lig B fordi strenge, som vi så i sidste uge, 340 00:15:25,600 --> 00:15:28,650 er array, så vi får den første tegn fra det. 341 00:15:28,650 --> 00:15:34,960 Så igen, hvis jeg udskrives almindelig tekst af Jeg, jeg gør i virkeligheden, får karakter 342 00:15:34,960 --> 00:15:36,560 B. Og det er pæn, ikke? 343 00:15:36,560 --> 00:15:40,380 Jeg har faktisk ikke almindelig tekst I. Det er ikke en af ​​de variabler, jeg sat 344 00:15:40,380 --> 00:15:42,950 eller initialiseret, men du kan udskrive ud af en hel række ting 345 00:15:42,950 --> 00:15:45,640 hvis du gerne vil. 346 00:15:45,640 --> 00:15:47,340 >> Men lad os komme igennem. 347 00:15:47,340 --> 00:15:50,050 Hvis almindelig tekst I er større end A og klartekst I er mindre end eller lig med 348 00:15:50,050 --> 00:15:53,290 Z, der klart er sandt, fordi vi har en kapital B. Jeg har tænkt mig at køre 349 00:15:53,290 --> 00:15:54,230 en kommando på den. 350 00:15:54,230 --> 00:15:58,530 Vi så, at matematik i sidste uge, så vi vil tager det for givet, at det virker 351 00:15:58,530 --> 00:16:00,900 ret i henhold til check 50 år. 352 00:16:00,900 --> 00:16:03,720 >> Disse krøllede parenteser, den første viste, at jeg var afslutter hvis 353 00:16:03,720 --> 00:16:07,030 tilstand, den anden viste at jeg forlader for-løkken. 354 00:16:07,030 --> 00:16:10,400 Og så nu når jeg ramte Dernæst vil vi se Vi er tilbage på for-løkken igen. 355 00:16:10,400 --> 00:16:11,970 Vi går gennem for loop igen. 356 00:16:11,970 --> 00:16:18,110 Lad os faktisk træde ind i anden iteration af for-løkken og type 357 00:16:18,110 --> 00:16:20,520 info lokale. 358 00:16:20,520 --> 00:16:22,190 >> Så vi er i den anden iteration vores for loop. 359 00:16:22,190 --> 00:16:24,530 Jeg er lig med 1, som vi forventer. 360 00:16:24,530 --> 00:16:26,650 N er lig med 6, som vi forventer. 361 00:16:26,650 --> 00:16:28,810 Key lig 3, som vi forventer. 362 00:16:28,810 --> 00:16:32,625 Og almindelig tekst, vil du se, lig EARFOO nu, ikke BARFOO længere, fordi 363 00:16:32,625 --> 00:16:37,930 i vores tidligere iteration, B var ændret til et stort E. Så vi er ved 364 00:16:37,930 --> 00:16:40,040 at støde på problemet, så det er, hvor vi kommer til at 365 00:16:40,040 --> 00:16:41,130 dykke ned i debugging. 366 00:16:41,130 --> 00:16:43,365 Men nogen har nogen spørgsmål om, hvad vi har gjort hidtil? 367 00:16:43,365 --> 00:16:46,770 368 00:16:46,770 --> 00:16:47,910 Fantastic. 369 00:16:47,910 --> 00:16:52,710 >> Så vi er ved at udføre dette, hvis betingelse, almindelig tekst beslag jeg lukkede 370 00:16:52,710 --> 00:16:57,500 beslag større end A og almindelig tekst I mindre end eller lig med Z. Men før 371 00:16:57,500 --> 00:17:00,450 Jeg går ind i det, fordi det er her Jeg kender min fejl er, vil jeg påpege 372 00:17:00,450 --> 00:17:06,859 ud almindelig tekst af I. Så lad os sætte udskrive. 373 00:17:06,859 --> 00:17:12,020 Det gør lig tegnet A, således at synes så langt, alt er godt og rigtigt. 374 00:17:12,020 --> 00:17:14,740 >> Så jeg forventer, at denne linje pr min logik, denne linje skal være sandt. 375 00:17:14,740 --> 00:17:16,099 Det er et stort bogstav. 376 00:17:16,099 --> 00:17:20,599 Men hvis jeg ramte n, vi indse, at dette linje, i virkeligheden, ikke udføre. 377 00:17:20,599 --> 00:17:22,609 Jeg sprang ned til andet, hvis. 378 00:17:22,609 --> 00:17:25,460 Hvorfor skete det? 379 00:17:25,460 --> 00:17:27,480 >> STUDENT: Fordi du har din tilstand af almindelig tekst er større 380 00:17:27,480 --> 00:17:29,130 end A, ikke lig med eller større end. 381 00:17:29,130 --> 00:17:32,260 >> JASON HIRSCHHORN: Så jeg havde min almindelig tekst I er større end A, ikke er større 382 00:17:32,260 --> 00:17:32,850 end eller lig med. 383 00:17:32,850 --> 00:17:38,130 Så klart, hovedstaden A ikke gjorde udløser dette, hvis tilstand, og det gjorde vi 384 00:17:38,130 --> 00:17:40,520 ikke træde ind i det, og det gjorde vi ikke gøre det nødvendige skift. 385 00:17:40,520 --> 00:17:41,360 Så det er det, faktisk. 386 00:17:41,360 --> 00:17:42,920 Jeg regnede ud af min bug. 387 00:17:42,920 --> 00:17:46,775 Jeg kunne gå tilbage i min kildefil, ændre det, og opdatere den og 388 00:17:46,775 --> 00:17:47,855 køre Tjek 50 igen. 389 00:17:47,855 --> 00:17:52,590 >> Men vi vil se, bare for pædagogik s skyld, hvis jeg holde. 390 00:17:52,590 --> 00:17:59,580 Det andet, hvis ikke udfører enten, men hvad stedet lig er kommandoen 391 00:17:59,580 --> 00:18:00,500 der ikke ændrer sig. 392 00:18:00,500 --> 00:18:04,840 Så det er ikke ændret på alle, og hvis jeg udskrive almindelig tekst her, vil vi se at gå 393 00:18:04,840 --> 00:18:08,250 ved at for-løkken ikke i virkeligheden, ændre det andet tegn på alle. 394 00:18:08,250 --> 00:18:09,600 Det er stadig en kapital A. 395 00:18:09,600 --> 00:18:12,690 >> Så igen, vi fejlrettet vores fejl. 396 00:18:12,690 --> 00:18:17,380 Vi indså, at der var vis logik mangler. 397 00:18:17,380 --> 00:18:20,590 Og vi fejlrettet det forud for tid, før faktisk udfører denne linje, 398 00:18:20,590 --> 00:18:24,320 men du ville have bemærket havde vi bare hit Next og hoppe til det andet, hvis 399 00:18:24,320 --> 00:18:26,710 det betyder, at at hvis betingelse var ikke sandt. 400 00:18:26,710 --> 00:18:29,550 Vi havde ikke i virkeligheden, får det resultat, vi havde forventet. 401 00:18:29,550 --> 00:18:33,240 Så vi kunne have været bedt om det, havde vi ikke været så klog, at se på 402 00:18:33,240 --> 00:18:38,510 at hvis tilstand og kontrollere, om i virkeligheden, vores tilstand bør evaluere på 403 00:18:38,510 --> 00:18:41,150 sandt i den aktuelle kontekst. 404 00:18:41,150 --> 00:18:42,880 >> Det er alt for debugging dette program. 405 00:18:42,880 --> 00:18:45,340 Er der nogen, der har nogen spørgsmål? 406 00:18:45,340 --> 00:18:50,486 Hvad kommando kunne jeg ramt at afslutte GDB? 407 00:18:50,486 --> 00:18:53,900 Q. Og så vil jeg blive bedt om, Afslut alligevel? 408 00:18:53,900 --> 00:18:54,390 Ja eller nej. 409 00:18:54,390 --> 00:18:58,440 Jeg får ramt ja, og jeg er holdt op GDB. 410 00:18:58,440 --> 00:19:00,860 >> Så det var en hurtig primer til GDB. 411 00:19:00,860 --> 00:19:03,430 Faktisk, i en virkelig situation, Jeg gjorde det på kontortid. 412 00:19:03,430 --> 00:19:06,710 Jeg GDBed netop dette program på kontortid med en elev. 413 00:19:06,710 --> 00:19:12,410 Og hvis vi går tilbage til de kommandoer, vi så før, vi brugte pause vigtigste først 414 00:19:12,410 --> 00:19:13,190 ting vi gjorde. 415 00:19:13,190 --> 00:19:16,060 Vi brugte køre med kommandolinjeargumenter, anden ting, vi gjorde. 416 00:19:16,060 --> 00:19:18,520 Vi brugte næste en masse at flytte os gennem linjer. 417 00:19:18,520 --> 00:19:20,310 Og igen, den korte version næste er n. 418 00:19:20,310 --> 00:19:22,920 Det er i parentes gråt på diaset. 419 00:19:22,920 --> 00:19:28,590 >> Vi brugte ikke skridt, men det gjorde vi ikke nødvendigvis i denne sag. 420 00:19:28,590 --> 00:19:32,150 Men vi kan bruge det i en lidt senere på i dag, hvis vi debugging for 421 00:19:32,150 --> 00:19:36,500 eksempel binær søgning, når binær søgning kaldes i en separat 422 00:19:36,500 --> 00:19:38,200 funktion, men der er nogle fejl med det. 423 00:19:38,200 --> 00:19:40,440 Vi kommer til at ønsker at træde ind i opkaldet til binær søgning og 424 00:19:40,440 --> 00:19:41,840 faktisk debug det. 425 00:19:41,840 --> 00:19:45,130 Liste vi ikke bruge enten fordi vi havde en god fornemmelse af vores kode, men hvis jeg 426 00:19:45,130 --> 00:19:48,420 ønskede at få en fornemmelse af, hvad kode jeg var omkring, kunne jeg bare bruge listen. 427 00:19:48,420 --> 00:19:50,310 >> Udskriv vi brugte, info locals vi brugt. 428 00:19:50,310 --> 00:19:53,260 Fortsæt vi ikke behøver at bruge i denne tilfælde heller ikke vi skal bruge 429 00:19:53,260 --> 00:19:55,060 deaktivere, men vi gjorde brug afslutte. 430 00:19:55,060 --> 00:19:57,850 Igen, disse 10 kommandoer, praktisere dem. 431 00:19:57,850 --> 00:20:00,770 Hvis du forstår disse 10 kommandoer, du skal være indstillet til debugging enhver 432 00:20:00,770 --> 00:20:02,525 Problem med GDB. 433 00:20:02,525 --> 00:20:05,230 434 00:20:05,230 --> 00:20:08,420 >> Så vi er ved at gå på igen, til det springende punkt i dag, at gå over 435 00:20:08,420 --> 00:20:09,720 disse sortering og søgning algoritmer. 436 00:20:09,720 --> 00:20:14,075 Før vi gør det, igen, spørgsmål, kommentarer, bekymringer for GDB? 437 00:20:14,075 --> 00:20:16,750 438 00:20:16,750 --> 00:20:20,960 Så er alle kommer til at bruge GDB snarere end printf? 439 00:20:20,960 --> 00:20:24,550 Så alle, for evighed skyld, alle nikker deres hoved ret 440 00:20:24,550 --> 00:20:27,400 nu, så jeg vil se dig på kontortid og alle TFS vil se dig og 441 00:20:27,400 --> 00:20:29,460 de vil sige, vise mig, hvordan man bruger GDB, og du vil være i stand 442 00:20:29,460 --> 00:20:31,240 at vise dem, right? 443 00:20:31,240 --> 00:20:31,760 Slags? 444 00:20:31,760 --> 00:20:32,640 Måske forhåbentlig. 445 00:20:32,640 --> 00:20:33,670 Fedt. 446 00:20:33,670 --> 00:20:35,790 >> Så vi kommer til at flytte ind sortering og søgning. 447 00:20:35,790 --> 00:20:40,710 Du vil se, at jeg har en liste allerede sorteres for os, men det vil ikke 448 00:20:40,710 --> 00:20:42,220 at være tilfældet altid. 449 00:20:42,220 --> 00:20:49,170 Så i det problem indstillet specifikation for problem sæt tre, du har shorts 450 00:20:49,170 --> 00:20:51,410 at du kan se, og det faktisk beder dig om at se disse shorts. 451 00:20:51,410 --> 00:20:55,090 Også i foredrag i sidste uge, gik vi over en masse af disse algoritmer, så jeg er 452 00:20:55,090 --> 00:20:59,150 ikke kommer til at tilbringe tid i klassen går i løbet af disse algoritmer igen eller tegning 453 00:20:59,150 --> 00:21:01,130 billeder til hvordan disse algoritmer virker. 454 00:21:01,130 --> 00:21:04,030 Igen, at oplysninger, kan du re-watch foredrag, eller at oplysninger 455 00:21:04,030 --> 00:21:08,570 er fanget fremragende på shorts for disse søgninger, som alle 456 00:21:08,570 --> 00:21:10,920 som er tilgængelige på cs50.net. 457 00:21:10,920 --> 00:21:14,200 >> Så i stedet for, hvad vi vil gøre, er at skrive disse programmer. 458 00:21:14,200 --> 00:21:18,190 Vi har en følelse, en mental model af, hvordan de arbejder, og så hvad vi vil 459 00:21:18,190 --> 00:21:20,210 at gøre, er at kode dem for alvor. 460 00:21:20,210 --> 00:21:23,430 Vi kommer til at dreje, at mental model, det billede, hvis du vil, i det 461 00:21:23,430 --> 00:21:24,960 faktiske kode. 462 00:21:24,960 --> 00:21:28,460 Og hvis du var lidt forvirret eller diset på det mentale model, jeg er helt 463 00:21:28,460 --> 00:21:28,770 forstå. 464 00:21:28,770 --> 00:21:30,540 >> Vi er faktisk ikke kommer til at springe til kode samme. 465 00:21:30,540 --> 00:21:36,030 Så mens denne prompt i dette dias spørger du at kode binær søgning, og 466 00:21:36,030 --> 00:21:39,470 faktisk en iterativ version af binær søgning, den første ting jeg 467 00:21:39,470 --> 00:21:42,370 virkelig ønsker dig at gøre, er skrive nogle pseudokode. 468 00:21:42,370 --> 00:21:47,020 Så du har denne mentale model hvordan binær søgning værker. 469 00:21:47,020 --> 00:21:50,060 Tag et ark papir, hvis du har en let tilgængelig, eller åbne en 470 00:21:50,060 --> 00:21:52,520 tekst editor, og jeg vil gerne alle til at skrive. 471 00:21:52,520 --> 00:21:57,470 Tage fire minutter til at skrive pseudokode for binær søgning. 472 00:21:57,470 --> 00:21:58,990 >> Igen, så tænk på, at mental model. 473 00:21:58,990 --> 00:22:01,980 Jeg kommer rundt, hvis du har spørgsmål og vi kan tegne billedet ud. 474 00:22:01,980 --> 00:22:06,220 Men først, før vi begynder at programmering, Jeg vil gerne skrive 475 00:22:06,220 --> 00:22:09,920 pseudokode for binær søgning, så når vi dykke i, har vi nogle retning som 476 00:22:09,920 --> 00:22:12,110 til, hvor vi skal lede. 477 00:22:12,110 --> 00:22:15,330 >> STUDENT: Kan vi antage den vifte af værdier, vi får, er allerede sorteres? 478 00:22:15,330 --> 00:22:17,960 >> JASON HIRSCHHORN: Så for binær søgning at arbejde - glimrende spørgsmål - du 479 00:22:17,960 --> 00:22:20,970 nødt til at tage i en sorteret matrix af værdier. 480 00:22:20,970 --> 00:22:22,290 Så antager det vil virke. 481 00:22:22,290 --> 00:22:23,480 Vi vil gå tilbage til dette dias. 482 00:22:23,480 --> 00:22:27,220 Du vil se i lilla funktionen erklæringen er bool binary_search int 483 00:22:27,220 --> 00:22:29,230 værdi, int værdier, int n. 484 00:22:29,230 --> 00:22:32,910 Dette bør ser bekendt, hvis du har allerede nærmede sig eller fået din 485 00:22:32,910 --> 00:22:34,580 hænder beskidte med problemet sæt. 486 00:22:34,580 --> 00:22:35,910 >> Men det er din funktion erklæring. 487 00:22:35,910 --> 00:22:39,080 Igen, ikke skulle have behov for at bekymre sig om at meget i dette øjeblik. 488 00:22:39,080 --> 00:22:43,660 Hvad jeg virkelig ønsker dig at gøre er at tage fire minutter til pseudokoden binær 489 00:22:43,660 --> 00:22:46,380 søge, og så vil vi gå over det som en gruppe. 490 00:22:46,380 --> 00:22:47,500 Og jeg vil komme rundt. 491 00:22:47,500 --> 00:22:49,590 Hvis du har spørgsmål, er du velkommen fri til at hæve din hånd. 492 00:22:49,590 --> 00:25:07,110 493 00:25:07,110 --> 00:25:09,680 >> Hvorfor tager du ikke tage to minutter mere at slutte op pseudokoden? 494 00:25:09,680 --> 00:25:13,690 495 00:25:13,690 --> 00:25:15,820 Jeg ved, at dette kan virke latterligt, at vi bruger så meget tid på 496 00:25:15,820 --> 00:25:20,350 noget, der er ikke engang faktisk i C, men især for disse mere 497 00:25:20,350 --> 00:25:24,030 udfordrende algoritmer og problem sæt, som vi er nødt til at regne ud, 498 00:25:24,030 --> 00:25:27,210 starter i pseudokode ikke bekymre om syntaksen, bare bekymre sig om 499 00:25:27,210 --> 00:25:29,150 logik, er utroligt hjælpsomme. 500 00:25:29,150 --> 00:25:32,720 Og på den måde, du er ikke at løse to utroligt vanskelige problemer på én gang. 501 00:25:32,720 --> 00:25:35,390 Du er bare fokusere på logik, og så du flytter ind i syntaks. 502 00:25:35,390 --> 00:25:59,960 503 00:25:59,960 --> 00:26:01,385 >> OK. 504 00:26:01,385 --> 00:26:03,680 Lad os begynde at gå igennem pseudokode. 505 00:26:03,680 --> 00:26:05,380 Jeg har skrevet op her, binær søg pseudokode. 506 00:26:05,380 --> 00:26:07,360 Vi skriver dette på bord sammen. 507 00:26:07,360 --> 00:26:10,040 Eller jeg vil skrive det, og du vil give mig anvisningerne, jeg har brug for. 508 00:26:10,040 --> 00:26:15,010 Så kan nogen give mig den første linje i pseudokode du 509 00:26:15,010 --> 00:26:18,350 skrev for binær søgning? 510 00:26:18,350 --> 00:26:20,258 Ja, Annie? 511 00:26:20,258 --> 00:26:22,698 >> STUDENT: Mens længden af listen er større end nul. 512 00:26:22,698 --> 00:26:26,114 513 00:26:26,114 --> 00:26:34,880 >> JASON HIRSCHHORN: Mens længden af listen er større end nul. 514 00:26:34,880 --> 00:26:38,810 Og igen ser vi nogle C-leder syntaktiske ting på her. 515 00:26:38,810 --> 00:26:41,550 Men det meste af dette er på engelsk. 516 00:26:41,550 --> 00:26:43,980 Har nogen har nogen linje de lægger før dette i deres pseudo-kode? 517 00:26:43,980 --> 00:26:47,280 518 00:26:47,280 --> 00:26:50,210 >> STUDENT: Få et array af sorteret numre. 519 00:26:50,210 --> 00:26:53,600 >> JASON HIRSCHHORN: Du skrev "får en vifte af sorterede numre. "Per den 520 00:26:53,600 --> 00:26:56,140 funktion erklæring, vil vi passerer et array af sorteret numre. 521 00:26:56,140 --> 00:26:57,280 >> STUDENT: [uhørligt]. 522 00:26:57,280 --> 00:26:59,030 >> JASON HIRSCHHORN: So vi vil have det. 523 00:26:59,030 --> 00:27:01,820 Men ja, hvis vi ikke har det, vi vil være nødvendigt at sortere vores udvalg af 524 00:27:01,820 --> 00:27:04,850 tal, fordi binær søgning kun virker på sorteret arrays. 525 00:27:04,850 --> 00:27:11,300 Så mens længden af ​​listen er lig med nul, er jeg kommer til at sætte nogle krøllede parenteser 526 00:27:11,300 --> 00:27:15,420 at gøre det ser lidt mere ligesom C. Men mens synes at kortlægge på en 527 00:27:15,420 --> 00:27:19,550 mens loop, så inde i dette, mens loop hvad skal vi 528 00:27:19,550 --> 00:27:22,000 gøre for binær søgning? 529 00:27:22,000 --> 00:27:25,530 >> Nogen andre, der ikke har givet mig en svar endnu, men der skrev dette? 530 00:27:25,530 --> 00:27:31,750 531 00:27:31,750 --> 00:27:33,320 >> STUDENT: Gå til midten af ​​listen. 532 00:27:33,320 --> 00:27:33,980 >> JASON HIRSCHHORN: Tom. 533 00:27:33,980 --> 00:27:35,230 Gå til midten af ​​listen. 534 00:27:35,230 --> 00:27:43,290 535 00:27:43,290 --> 00:27:45,530 Og opfølgende spørgsmål, hvad gør vi, når vi er på 536 00:27:45,530 --> 00:27:46,870 midt på listen? 537 00:27:46,870 --> 00:27:49,310 >> STUDENT: Har en check, om der er det nummer, du leder efter. 538 00:27:49,310 --> 00:27:50,120 >> JASON HIRSCHHORN: Excellent. 539 00:27:50,120 --> 00:28:05,500 Gå midt på listen, og tjek hvis vores værdi er der - 540 00:28:05,500 --> 00:28:06,515 fantastisk. 541 00:28:06,515 --> 00:28:10,460 Har nogen har noget andet der var anderledes end dette? 542 00:28:10,460 --> 00:28:11,210 Det er helt rigtigt. 543 00:28:11,210 --> 00:28:13,800 >> Det første, vi gør i binær søgning er at gå til midten af ​​listen og 544 00:28:13,800 --> 00:28:15,870 at se, om vores værdi er der. 545 00:28:15,870 --> 00:28:19,682 Så jeg antager, hvis vores værdi er der, hvad gør vi? 546 00:28:19,682 --> 00:28:21,610 >> STUDENT: Vi vender tilbage nul [uhørligt]. 547 00:28:21,610 --> 00:28:23,400 >> JASON HIRSCHHORN: Ja, hvis vores værdien er der, vi fandt det. 548 00:28:23,400 --> 00:28:27,950 Så vi kan fortælle en eller anden måde, men dette funktion er defineret, vi fortælle brugeren 549 00:28:27,950 --> 00:28:28,520 vi fandt det. 550 00:28:28,520 --> 00:28:30,950 Hvis det ikke er der, selvom, det er hvor det bliver tricky. 551 00:28:30,950 --> 00:28:35,120 Så hvis det ikke er der, en anden, der arbejdede på binær søgning eller 552 00:28:35,120 --> 00:28:36,830 har en idé nu, hvad gør vi? 553 00:28:36,830 --> 00:28:37,830 >> STUDENT: Spørgsmål. 554 00:28:37,830 --> 00:28:38,100 >> JASON HIRSCHHORN: Ja? 555 00:28:38,100 --> 00:28:39,920 >> STUDENT: Er array allerede sorteres? 556 00:28:39,920 --> 00:28:42,200 >> JASON HIRSCHHORN: Ja, vi antager array allerede sorteret. 557 00:28:42,200 --> 00:28:46,480 >> STUDENT: Så du er nødt til at kontrollere, om den værdi, du ser, er større end 558 00:28:46,480 --> 00:28:51,745 den værdi, du ønsker, kan du flytte til midten af ​​den anden halvdel. 559 00:28:51,745 --> 00:28:54,110 >> JASON HIRSCHHORN: Så hvis midten af listen er større end hvad vi 560 00:28:54,110 --> 00:28:57,440 søger, så vi hvad? 561 00:28:57,440 --> 00:28:58,320 Vi bevæger hvor? 562 00:28:58,320 --> 00:29:01,400 >> STUDENT: Du ønsker at flytte til den halvdel af listen med 563 00:29:01,400 --> 00:29:02,780 lavere antal end det. 564 00:29:02,780 --> 00:29:04,460 >> JASON HIRSCHHORN: Så vi vil kalde det venstre. 565 00:29:04,460 --> 00:29:15,435 Så hvis midten er større, kan vi søge venstre halvdel af listen. 566 00:29:15,435 --> 00:29:20,620 567 00:29:20,620 --> 00:29:22,980 Og derefter ved søgning, hvad mener jeg med søgning? 568 00:29:22,980 --> 00:29:24,010 >> STUDENT: [uhørligt]. 569 00:29:24,010 --> 00:29:24,410 >> JASON HIRSCHHORN: Vi går til midten. 570 00:29:24,410 --> 00:29:25,740 Vi har faktisk gentage denne ting. 571 00:29:25,740 --> 00:29:29,210 Vi går tilbage gennem vores while-løkke. 572 00:29:29,210 --> 00:29:31,480 Jeg vil give dig den sidste - 573 00:29:31,480 --> 00:29:39,047 andet, hvis midten er mindre end hvad vi gør, hvad gør vi her? 574 00:29:39,047 --> 00:29:40,360 >> STUDENT: Gå til højre. 575 00:29:40,360 --> 00:29:41,610 >> JASON HIRSCHHORN: Søg til højre. 576 00:29:41,610 --> 00:29:47,440 577 00:29:47,440 --> 00:29:51,710 Det ser godt ud, men nogen har noget, som vi kan mangle eller 578 00:29:51,710 --> 00:29:53,200 noget andet, som du sætter i din pseudo-kode? 579 00:29:53,200 --> 00:29:57,080 580 00:29:57,080 --> 00:29:58,410 Så dette er hvad vi har hidtil. 581 00:29:58,410 --> 00:30:00,960 Mens længden af ​​listen er større end nul, vi kommer til at gå 582 00:30:00,960 --> 00:30:03,220 til midten af ​​listen og kontrollere, om vores værdi er der. 583 00:30:03,220 --> 00:30:06,970 >> Hvis den midterste er større, vil vi søg venstre, ellers hvis midten er 584 00:30:06,970 --> 00:30:09,230 mindre, vi kommer til at søge mod højre. 585 00:30:09,230 --> 00:30:14,430 Så vi har alle haft et vist kendskab til de vilkår, vi bruger i datalogi 586 00:30:14,430 --> 00:30:15,550 og de værktøjer, vi har. 587 00:30:15,550 --> 00:30:18,300 Men du vil allerede mærke at vi var tale på engelsk, men vi fandt en 588 00:30:18,300 --> 00:30:24,790 masse ting, som syntes at kortlægge på redskaber, vi har i vores kodning værktøjskasse. 589 00:30:24,790 --> 00:30:27,210 Så ret off the bat, vi er ikke vil faktisk kode endnu. 590 00:30:27,210 --> 00:30:33,300 >> Hvad ser vi her på engelsk, at kortene på ting, vi kan skrive i C? 591 00:30:33,300 --> 00:30:34,560 >> STUDENT: Mens. 592 00:30:34,560 --> 00:30:35,320 >> JASON HIRSCHHORN: Mens. 593 00:30:35,320 --> 00:30:40,610 Så dette, mens lige her kort på hvad? 594 00:30:40,610 --> 00:30:42,630 >> STUDENT: En while-løkke. 595 00:30:42,630 --> 00:30:43,200 >> JASON HIRSCHHORN: Et stykke loop? 596 00:30:43,200 --> 00:30:44,540 Eller sandsynligvis mere generelt en løkke. 597 00:30:44,540 --> 00:30:46,260 Vi ønsker at gøre noget igen og igen. 598 00:30:46,260 --> 00:30:49,050 Så vi kommer til at kode en løkke. 599 00:30:49,050 --> 00:30:51,640 Og vi allerede kender, fordi vi har gjort dette et par gange, og vi 600 00:30:51,640 --> 00:30:54,180 har masser af eksempler derude, hvor faktisk at skrive 601 00:30:54,180 --> 00:30:55,310 dette indeks til en sløjfe. 602 00:30:55,310 --> 00:30:56,160 Så det bør være temmelig nemt. 603 00:30:56,160 --> 00:30:58,070 Vi bør være i stand til at få det startede temmelig hurtigt. 604 00:30:58,070 --> 00:31:01,830 >> Hvad ser vi her? 605 00:31:01,830 --> 00:31:06,820 Hvilke andre strukturer grammatikker, tingene at vi er bekendt med i C, så gør vi 606 00:31:06,820 --> 00:31:09,790 allerede har en følelse af baseret off af de ord, vi har brugt? 607 00:31:09,790 --> 00:31:10,830 Ja, Anna? 608 00:31:10,830 --> 00:31:11,360 [Uhørligt] 609 00:31:11,360 --> 00:31:12,990 just kidding. 610 00:31:12,990 --> 00:31:13,540 Anna, gå videre. 611 00:31:13,540 --> 00:31:14,530 >> STUDENT: Hvis og andet. 612 00:31:14,530 --> 00:31:16,260 >> JASON HIRSCHHORN: Hvis og andet - lige her. 613 00:31:16,260 --> 00:31:18,840 Så hvad gør de ud? 614 00:31:18,840 --> 00:31:20,420 >> STUDENT: An hvis ellers erklæring. 615 00:31:20,420 --> 00:31:21,560 >> JASON HIRSCHHORN: Ja, betingelser, right? 616 00:31:21,560 --> 00:31:24,650 Så vi vil sandsynligvis nødt til at skrive nogle betingelser. 617 00:31:24,650 --> 00:31:31,185 Og igen, selvom måske forvirrende ved første, vi generelt har en mening nu 618 00:31:31,185 --> 00:31:34,010 af hvordan man skriver betingelser og syntaksen for forhold. 619 00:31:34,010 --> 00:31:36,850 Og hvis vi ikke gør det, vi bare kigge op syntaks for forhold, klippe og indsætte 620 00:31:36,850 --> 00:31:39,950 at fordi vi ved, at vi brug for en betingelse her. 621 00:31:39,950 --> 00:31:44,910 Alle andre ting, vi ser, at kortet på ting, vi måske nødt til at gøre i C? 622 00:31:44,910 --> 00:31:48,312 623 00:31:48,312 --> 00:31:48,960 Ja, Aleha? 624 00:31:48,960 --> 00:31:50,370 >> STUDENT: Det kan være indlysende, ved blot at kontrollere, hvis en 625 00:31:50,370 --> 00:31:51,990 værdi er lig med noget. 626 00:31:51,990 --> 00:31:54,578 >> JASON HIRSCHHORN: Så hvordan kan vi kontrollere og - så gå til midten af ​​listen 627 00:31:54,578 --> 00:31:55,610 og kontrollere, hvis vores værdi er der? 628 00:31:55,610 --> 00:31:56,570 Hvordan gør vi det i C? 629 00:31:56,570 --> 00:31:58,450 Hvad er syntaksen for det? 630 00:31:58,450 --> 00:31:59,235 >> STUDENT: Lig, lig. 631 00:31:59,235 --> 00:32:00,650 >> JASON HIRSCHHORN: Lig, lig. 632 00:32:00,650 --> 00:32:03,540 Så denne kontrol er sandsynligvis kommer at være et lighedstegn, lig. 633 00:32:03,540 --> 00:32:04,510 Så vi vil vide, at vi har brug for, at et eller andet sted. 634 00:32:04,510 --> 00:32:07,510 Og faktisk, bare i at skrive det, vi ser de andre ting. 635 00:32:07,510 --> 00:32:11,400 Vi er nødt til at gøre nogle sammenligning operatører derinde - 636 00:32:11,400 --> 00:32:12,010 fantastisk. 637 00:32:12,010 --> 00:32:14,980 Så det faktisk ser ud, ved og stor, har vi ikke skrevet en 638 00:32:14,980 --> 00:32:16,390 ord af C-kode endnu. 639 00:32:16,390 --> 00:32:20,610 Men vi fik den mentale model ned via foredrag og disse shorts. 640 00:32:20,610 --> 00:32:22,350 >> Vi skrev pseudo-kode som en gruppe. 641 00:32:22,350 --> 00:32:27,110 Og allerede, vi har 80%, hvis ikke 90% af, hvad vi skal gøre. 642 00:32:27,110 --> 00:32:28,550 Nu er vi bare nødt til at kode det, som igen er en 643 00:32:28,550 --> 00:32:30,110 ikke-trivielt problem at løse. 644 00:32:30,110 --> 00:32:31,890 Men i det mindste er vi fast på logik. 645 00:32:31,890 --> 00:32:38,040 Mindst nu når vi går til kontortid, Jeg kan sige, jeg ved hvad jeg har brug for 646 00:32:38,040 --> 00:32:40,160 at gøre, men du kan minde mig af syntaksen? 647 00:32:40,160 --> 00:32:42,940 Eller selv om der overfyldt kontortid, du kan google for syntaks, snarere 648 00:32:42,940 --> 00:32:45,040 end at blive hængende på logik. 649 00:32:45,040 --> 00:32:48,570 >> Og igen, snarere end at forsøge at løse logik og syntaks problemer alle 650 00:32:48,570 --> 00:32:51,900 på én gang, er det ofte meget bedre at bryde disse to vanskelige problemer ud i 651 00:32:51,900 --> 00:32:58,280 to mere håndterbare dem og gøre det pseudokode først og derefter kode i C. 652 00:32:58,280 --> 00:33:00,620 Så lad os se, hvad jeg gjorde for pseudo-kode i forvejen. 653 00:33:00,620 --> 00:33:04,060 >> Mens længden af ​​listen er større end nul, se på den midterste 654 00:33:04,060 --> 00:33:05,090 af listen. 655 00:33:05,090 --> 00:33:09,610 Hvis antallet fundet returnerede sandt, ellers hvis tal højere, søg venstre. 656 00:33:09,610 --> 00:33:13,200 Else hvis antallet er lavere, søg højre, return false. 657 00:33:13,200 --> 00:33:18,710 Så ser næsten identiske, hvis ikke næsten identisk med, hvad vi skrev. 658 00:33:18,710 --> 00:33:23,030 Faktisk, Tom, hvad du sagde først, bryde midten af ​​listen, og hvis 659 00:33:23,030 --> 00:33:24,880 nummer findes i to erklæringer er faktisk, hvad jeg gjorde. 660 00:33:24,880 --> 00:33:25,507 >> Jeg kombinerede dem der. 661 00:33:25,507 --> 00:33:27,100 Jeg skulle have lyttet til du første gang. 662 00:33:27,100 --> 00:33:30,640 Så det er pseudo-kode, vi har. 663 00:33:30,640 --> 00:33:35,060 Hvis du ønsker at nu, undskyld, gå tilbage til vores oprindelige problem. 664 00:33:35,060 --> 00:33:37,780 Lad os kode binary.c. 665 00:33:37,780 --> 00:33:40,870 Så implementere en iterativ udgave af binær søgning ved hjælp af følgende 666 00:33:40,870 --> 00:33:42,420 funktion erklæring. 667 00:33:42,420 --> 00:33:44,550 >> Og du behøver ikke at kopiere det ned endnu. 668 00:33:44,550 --> 00:33:49,470 Jeg er faktisk kommer til at åbne op lige her binary.c. 669 00:33:49,470 --> 00:33:52,880 Så der er den funktion erklæring i midten af ​​skærmen. 670 00:33:52,880 --> 00:33:57,570 Og du vil se, at jeg tog pseudo-kode fra på mine sider, men næsten identiske 671 00:33:57,570 --> 00:33:59,740 til, hvad vi skrev, og sætte det i for dig. 672 00:33:59,740 --> 00:34:06,010 Så nu, lad os tage fem minutter at kode denne funktion. 673 00:34:06,010 --> 00:34:08,199 >> Og igen, hvis du har spørgsmål, hæve din hånd, lad mig vide, vil jeg 674 00:34:08,199 --> 00:34:08,710 kommer rundt. 675 00:34:08,710 --> 00:34:09,800 >> STUDENT: [uhørligt]. 676 00:34:09,800 --> 00:34:12,380 >> JASON HIRSCHHORN: Så jeg tog den binære søg definition på 677 00:34:12,380 --> 00:34:14,429 top, på linje 12. 678 00:34:14,429 --> 00:34:16,429 Det er, hvad jeg fik for mine dias. 679 00:34:16,429 --> 00:34:20,940 Og så alt dette pseudo-kode jeg lige kopieres og indsættes fra dias, 680 00:34:20,940 --> 00:34:22,190 pseudo-kode dias. 681 00:34:22,190 --> 00:35:22,830 682 00:35:22,830 --> 00:35:26,786 Jeg er stadig ikke høre [uhørligt]. 683 00:35:26,786 --> 00:37:13,010 684 00:37:13,010 --> 00:37:15,820 >> Så hvis du er færdig med din implementering, vil jeg tjekke det. 685 00:37:15,820 --> 00:37:19,410 Jeg mailede dig helpers.h fil tidligere i denne klasse. 686 00:37:19,410 --> 00:37:22,360 Og det vil være tilgængelige online såvel til download for mennesker ser 687 00:37:22,360 --> 00:37:24,750 denne sektion tid forsinket. 688 00:37:24,750 --> 00:37:29,350 Og jeg brugte bare den generiske fordeling kode fra pset3. 689 00:37:29,350 --> 00:37:34,590 Så jeg tog find.C, bruge min helpers.h fil snarere end helpers.h fil 690 00:37:34,590 --> 00:37:36,280 der er givet i fordelingen kode. 691 00:37:36,280 --> 00:37:39,310 >> Og jeg havde at gøre en anden ændring i find.C snarere end at ringe simpelthen 692 00:37:39,310 --> 00:37:42,770 søg, ring binary_search. 693 00:37:42,770 --> 00:37:49,080 Så hvis du ønsker at teste din kode, vide, at det er sådan, man gør det. 694 00:37:49,080 --> 00:37:52,530 I virkeligheden, når vi skal køre denne kode lige nu, jeg har lige lavet en kopi af 695 00:37:52,530 --> 00:37:59,820 min pset3 mappe, igen, byttet ud de hjælpere filer og derefter foretaget, at 696 00:37:59,820 --> 00:38:04,695 ændre i find.C at kalde binary_search snarere end blot at søge. 697 00:38:04,695 --> 00:40:08,620 698 00:40:08,620 --> 00:40:09,120 >> JASON HIRSCHHORN: Ja. 699 00:40:09,120 --> 00:40:11,258 Har du spørgsmål? 700 00:40:11,258 --> 00:40:12,150 >> STUDENT: Nevermind. 701 00:40:12,150 --> 00:40:12,600 >> JASON HIRSCHHORN: Ingen bekymringer. 702 00:40:12,600 --> 00:40:13,370 Nå, lad os komme i gang. 703 00:40:13,370 --> 00:40:15,090 Vi vil kode det som en gruppe. 704 00:40:15,090 --> 00:40:16,050 En anden tone. 705 00:40:16,050 --> 00:40:20,600 Igen, dette er, kan nemt byttes i for Problem Set Tre. 706 00:40:20,600 --> 00:40:25,530 Jeg har min helpers.h fil, som snarere end helpers.h vi er givet, 707 00:40:25,530 --> 00:40:28,560 erklærer binær søgning, boble sortere og udvælgelse slags. 708 00:40:28,560 --> 00:40:37,400 Og i find.c du vil opdage på linje, hvad er det, linje 68, vi kalder binær 709 00:40:37,400 --> 00:40:39,160 søg snarere end søgning. 710 00:40:39,160 --> 00:40:42,930 Så igen, den kode, der er til rådighed online eller den kode, du er 711 00:40:42,930 --> 00:40:46,590 skaber lige nu let kan byttes i for p sæt 3 til at tjekke det. 712 00:40:46,590 --> 00:40:50,620 >> Men først, lad os kode binær søgning. 713 00:40:50,620 --> 00:40:53,690 Vores funktion erklæring, vi returnere en bool. 714 00:40:53,690 --> 00:40:55,810 Vi tager et heltal kaldet værdi. 715 00:40:55,810 --> 00:40:59,285 Vi tager et array af heltal kaldet værdier, og vi tager n være 716 00:40:59,285 --> 00:41:00,850 størrelsen af ​​matrixen. 717 00:41:00,850 --> 00:41:05,640 På linje 10, lige her, jeg har skarp omfatter stdbool.h. 718 00:41:05,640 --> 00:41:07,360 Er der nogen vide, hvorfor det er der? 719 00:41:07,360 --> 00:41:12,180 720 00:41:12,180 --> 00:41:16,600 Så hvad betyder det linje kode gøre? 721 00:41:16,600 --> 00:41:19,880 >> STUDENT: Det giver dig mulighed for at bruge en bool returtype. 722 00:41:19,880 --> 00:41:20,350 >> JASON HIRSCHHORN: Præcis. 723 00:41:20,350 --> 00:41:22,300 >> STUDENT: Eller det er et bibliotek, der giver mulighed at anvende en bool returtype. 724 00:41:22,300 --> 00:41:27,590 >> JASON HIRSCHHORN: Så den skarpe omfatte stdbool.h linje giver mig nogle 725 00:41:27,590 --> 00:41:31,340 definitioner og erklæringer for ting at jeg får lov til at bruge i 726 00:41:31,340 --> 00:41:32,400 dette bibliotek. 727 00:41:32,400 --> 00:41:36,570 Så blandt dem siger, at der er denne type kaldes bool, og det kan være 728 00:41:36,570 --> 00:41:37,750 sandt eller falsk. 729 00:41:37,750 --> 00:41:39,010 Så det er hvad denne linje gør. 730 00:41:39,010 --> 00:41:41,680 Og hvis jeg ikke havde denne linje, jeg ville komme i problemer for at skrive dette 731 00:41:41,680 --> 00:41:43,520 ord lige her, bool, lige der. 732 00:41:43,520 --> 00:41:44,140 Præcis højre. 733 00:41:44,140 --> 00:41:46,430 Så jeg har brug for, at der i denne kode. 734 00:41:46,430 --> 00:41:47,690 OK. 735 00:41:47,690 --> 00:41:51,860 Så dette igen, er en iterativ version, der ikke en rekursiv én. 736 00:41:51,860 --> 00:41:53,820 Så lad os komme i gang. 737 00:41:53,820 --> 00:41:56,200 >> Lad os starte med denne første linje pseudokode. 738 00:41:56,200 --> 00:41:58,770 Og forhåbentlig vil vi - eller ikke forhåbentlig. 739 00:41:58,770 --> 00:42:00,530 Vi kommer til at gå rundt i lokalet. 740 00:42:00,530 --> 00:42:05,110 Vi vil gå linje for linje, og jeg vil hjælpe du regne ud den linje, vi har brug for 741 00:42:05,110 --> 00:42:06,310 skrive først. 742 00:42:06,310 --> 00:42:10,550 Så mens længden af ​​listen er større end nul. 743 00:42:10,550 --> 00:42:12,680 Lad os starte i front. 744 00:42:12,680 --> 00:42:15,190 Hvilken linje skal jeg skrive her, i koden? 745 00:42:15,190 --> 00:42:19,470 >> STUDENT: Mens parentes n er større end 0. 746 00:42:19,470 --> 00:42:21,900 >> JASON HIRSCHHORN: Mens n er stor end 0. 747 00:42:21,900 --> 00:42:26,550 Så n er størrelsen af ​​en liste, og vi tjekker, om - 748 00:42:26,550 --> 00:42:26,800 >> [indskyde STEMMER] 749 00:42:26,800 --> 00:42:27,660 >> JASON HIRSCHHORN: - undskyld? 750 00:42:27,660 --> 00:42:29,360 >> STUDENT: Hvordan kan vi vide, at n er størrelsen på listen? 751 00:42:29,360 --> 00:42:29,690 >> JASON HIRSCHHORN: Undskyld. 752 00:42:29,690 --> 00:42:34,690 Per PSET specifikationen søgningen og sortere funktioner du har brug for at skrive, 753 00:42:34,690 --> 00:42:36,230 n er størrelsen på listen. 754 00:42:36,230 --> 00:42:37,710 Jeg glemte at forklare det her. 755 00:42:37,710 --> 00:42:41,310 Men ja. n er størrelsen af listen, i dette tilfælde. 756 00:42:41,310 --> 00:42:44,740 Så mens n er større end 0. 757 00:42:44,740 --> 00:42:45,580 OK. 758 00:42:45,580 --> 00:42:50,090 Det kan vise sig lidt problematisk selv, hvis tingene går videre. 759 00:42:50,090 --> 00:42:54,510 Fordi vi vil fortsætte med at kende størrelsen på listen i denne 760 00:42:54,510 --> 00:43:06,640 funktion, men siger vi starter med en vifte af 5 heltal. 761 00:43:06,640 --> 00:43:08,950 Og vi går igennem, og vi har nu indsnævret det ned til 762 00:43:08,950 --> 00:43:10,310 et array af to heltal. 763 00:43:10,310 --> 00:43:12,160 Hvilket 2 heltal er det? 764 00:43:12,160 --> 00:43:15,895 Størrelsen er 2 nu, at vi ønsker at se på, men som 2 er, at? 765 00:43:15,895 --> 00:43:17,720 Giver det mening, det spørgsmål? 766 00:43:17,720 --> 00:43:18,020 >> OK. 767 00:43:18,020 --> 00:43:19,120 Jeg spørger igen. 768 00:43:19,120 --> 00:43:26,640 Så vi starter med denne række af 5 heltal, og n er lig med 5, right? 769 00:43:26,640 --> 00:43:28,050 Vi kører igennem her. 770 00:43:28,050 --> 00:43:31,560 vi sandsynligvis ændre størrelsen, ret, da tingene går videre. 771 00:43:31,560 --> 00:43:32,700 Hvilket er, hvad vi siger, vi ønsker at gøre. 772 00:43:32,700 --> 00:43:34,150 Vi ønsker ikke at søge fuld ting igen. 773 00:43:34,150 --> 00:43:35,480 Så siger vi ændre det til 2.. 774 00:43:35,480 --> 00:43:36,970 Vi tager halvdelen af ​​den liste, der er mærkeligt. 775 00:43:36,970 --> 00:43:38,800 Så bare vælge 2. 776 00:43:38,800 --> 00:43:40,590 Så nu n er 2. 777 00:43:40,590 --> 00:43:42,780 Jeg undskylder for de fattige tør slette markører. 778 00:43:42,780 --> 00:43:43,080 Right? 779 00:43:43,080 --> 00:43:45,670 Og vi søger gennem listen igen med en liste over str. 2. 780 00:43:45,670 --> 00:43:48,580 Tja, vores array er stadig af str. 5. 781 00:43:48,580 --> 00:43:51,920 Vi siger, at vi kun ønsker at søg 2 pletter i det. 782 00:43:51,920 --> 00:43:53,590 Så der 2 spots er dem? 783 00:43:53,590 --> 00:43:57,640 784 00:43:57,640 --> 00:43:58,815 >> Giver det mening? 785 00:43:58,815 --> 00:44:00,290 Er de venstre 2 spots? 786 00:44:00,290 --> 00:44:01,940 Er det de rigtige 2 spots? 787 00:44:01,940 --> 00:44:03,540 Er de de 2 midterste spots? 788 00:44:03,540 --> 00:44:06,350 Vi har brudt problemet ned, men vi faktisk ikke ved, hvilken del af 789 00:44:06,350 --> 00:44:11,600 det problem, vi stadig kigger på, bare ved at have disse to variable. 790 00:44:11,600 --> 00:44:16,450 Så vi har brug for lidt mere derefter, mens n er større end 0. 791 00:44:16,450 --> 00:44:21,410 Vi har brug for at vide, hvor der n er i vores faktiske array. 792 00:44:21,410 --> 00:44:26,660 >> Så nogen har en skifte til denne linje? 793 00:44:26,660 --> 00:44:27,970 Det meste af denne linje er helt korrekt. 794 00:44:27,970 --> 00:44:29,170 Er der en anden tilføjelse? 795 00:44:29,170 --> 00:44:32,510 Kan vi bytte noget ud for n til gøre denne linje en smule bedre? 796 00:44:32,510 --> 00:44:32,865 Mm-hm? 797 00:44:32,865 --> 00:44:38,040 >> STUDENT: Kan du initialisere en variabel såsom længde til n, der vil så blive brugt 798 00:44:38,040 --> 00:44:39,600 senere i funktion? 799 00:44:39,600 --> 00:44:42,060 >> JASON HIRSCHHORN: Så initialisere en variabel længde n, 800 00:44:42,060 --> 00:44:42,900 og vi bruger det senere? 801 00:44:42,900 --> 00:44:47,070 Men så har vi bare opdatere længde og vi stadig løbe ind i dette problem, hvor vi 802 00:44:47,070 --> 00:44:51,180 skære ned på længden af ​​vores problem, men vi ved aldrig, hvor, faktisk, 803 00:44:51,180 --> 00:44:52,510 denne længde kort på. 804 00:44:52,510 --> 00:44:54,790 >> STUDENT: Er det ikke kommer til at ske senere, når du siger, søg venstre, 805 00:44:54,790 --> 00:44:55,746 søg ret? 806 00:44:55,746 --> 00:44:57,640 Du kommer til at gå til en anden område af dit - 807 00:44:57,640 --> 00:44:59,110 >> JASON HIRSCHHORN: Vi kommer til at gå til et område, men hvordan kan vi vide 808 00:44:59,110 --> 00:45:01,150 der er til at gå til? 809 00:45:01,150 --> 00:45:03,800 Hvis vi kun har array, og dette n, hvordan kan vi vide, hvor man 810 00:45:03,800 --> 00:45:05,050 gå i arrayet. 811 00:45:05,050 --> 00:45:05,900 I ryggen, ja? 812 00:45:05,900 --> 00:45:07,507 >> STUDENT: Har du, ligesom, en lavere grænse og en øvre grænse variabel eller 813 00:45:07,507 --> 00:45:08,586 sådan noget? 814 00:45:08,586 --> 00:45:09,060 >> JASON HIRSCHHORN: OK. 815 00:45:09,060 --> 00:45:10,780 Så dette er en anden idé. 816 00:45:10,780 --> 00:45:13,490 Snarere end blot at holde styr på størrelse, vi holde styr på den nedre og 817 00:45:13,490 --> 00:45:14,770 øvre grænse variabel. 818 00:45:14,770 --> 00:45:17,840 Så hvordan kan vi beregne størrelsen fra en nedre grænse og øvre grænse? 819 00:45:17,840 --> 00:45:18,520 >> [indskyde STEMMER] 820 00:45:18,520 --> 00:45:19,710 >> JASON HIRSCHHORN: subtraktion. 821 00:45:19,710 --> 00:45:23,650 Og også at holde styr på den nederste bundet og øvre grænse at lade os vide, 822 00:45:23,650 --> 00:45:26,215 Vi søger disse to? 823 00:45:26,215 --> 00:45:28,220 Er vi søger disse to herovre? 824 00:45:28,220 --> 00:45:29,540 Er vi søge på to midten? 825 00:45:29,540 --> 00:45:32,810 Sandsynligvis ikke de to midterste, fordi dette i virkeligheden er binær søgning. 826 00:45:32,810 --> 00:45:37,320 Men nu vil vi være i stand til at få den størrelse, men også for rammerne af arrayet. 827 00:45:37,320 --> 00:45:40,020 I det væsentlige, hvis vi har vores kæmpe telefonbog, vi rippe den i halve. 828 00:45:40,020 --> 00:45:42,990 Vi ved nu, hvor der er mindre telefonbog er. 829 00:45:42,990 --> 00:45:45,260 Men vi er faktisk ikke rippe telefonbogen i halve. 830 00:45:45,260 --> 00:45:48,570 Vi har stadig brug for at vide, hvor nye grænser for vores problem er. 831 00:45:48,570 --> 00:45:51,645 Er der nogen har nogen spørgsmål om det? 832 00:45:51,645 --> 00:45:52,440 Ja? 833 00:45:52,440 --> 00:45:56,020 >> STUDENT: Ville det fungere ved at skabe en variabel, i, at man så bare flytte 834 00:45:56,020 --> 00:46:00,770 stilling i forhold til dens aktuelle position, og længden, n? 835 00:46:00,770 --> 00:46:01,710 >> JASON HIRSCHHORN: Og hvad er jeg? 836 00:46:01,710 --> 00:46:04,110 >> STUDENT: Ligesom jeg er ligesom en slags - 837 00:46:04,110 --> 00:46:08,040 Ligesom du ville initialisere jeg at være den midterstilling af matrixen. 838 00:46:08,040 --> 00:46:12,540 Og derefter, hvis værdien på position i i midten af ​​arrayet i fundet 839 00:46:12,540 --> 00:46:17,870 være mindre end den værdi, du har brug for, jeg nu bliver længden af ​​array plus 840 00:46:17,870 --> 00:46:19,215 værdien af ​​i divideres med 2. 841 00:46:19,215 --> 00:46:20,270 Ligesom, se du skifte i - 842 00:46:20,270 --> 00:46:20,770 >> JASON HIRSCHHORN: Right. 843 00:46:20,770 --> 00:46:21,165 >> STUDENT: - op til - 844 00:46:21,165 --> 00:46:24,010 >> JASON HIRSCHHORN: Så jeg er næsten positive, der vil arbejde. 845 00:46:24,010 --> 00:46:26,800 Men pointen væsen, skal du to stykker af information her. 846 00:46:26,800 --> 00:46:30,050 Du kan gøre det med begyndelsen og slutningen, eller du kan gøre det med størrelse, og derefter 847 00:46:30,050 --> 00:46:31,060 nogle markør. 848 00:46:31,060 --> 00:46:32,630 Men du behøver to stykker af information her. 849 00:46:32,630 --> 00:46:34,160 Du kan ikke komme af med blot én. 850 00:46:34,160 --> 00:46:35,830 Betyder det giver mening? 851 00:46:35,830 --> 00:46:39,560 >> Så vi kommer til at gå igennem, og vi kommer til at gøre [uhørligt] 852 00:46:39,560 --> 00:46:41,330 og skabe nogle markører. 853 00:46:41,330 --> 00:46:42,690 Hvad lavede du skriver i din kode? 854 00:46:42,690 --> 00:46:46,190 >> STUDENT: Jeg sagde bare int bundet en er lig med 0. 855 00:46:46,190 --> 00:46:47,790 >> JASON HIRSCHHORN: Lad os kalde at int, begynder. 856 00:46:47,790 --> 00:46:49,140 >> STUDENT: OK. 857 00:46:49,140 --> 00:46:50,590 >> JASON HIRSCHHORN: Det gør mere mening for mig. 858 00:46:50,590 --> 00:46:51,670 Og? 859 00:46:51,670 --> 00:46:54,340 >> STUDENT: Jeg sagde, jeg gætte, int slutter. 860 00:46:54,340 --> 00:46:55,870 >> JASON HIRSCHHORN: int slutter. 861 00:46:55,870 --> 00:46:57,640 >> STUDENT: Jeg gætter på, n minus 1, eller noget lignende. 862 00:46:57,640 --> 00:46:59,100 Ligesom, det sidste element. 863 00:46:59,100 --> 00:47:02,310 >> JASON HIRSCHHORN: Så du skrev, int begynder lig 0 semikolon og int 864 00:47:02,310 --> 00:47:04,320 slutning er lig n minus 1, semikolon. 865 00:47:04,320 --> 00:47:06,850 Så det væsentlige, hvad vi gør her, 0 den første position. 866 00:47:06,850 --> 00:47:09,570 Og som vi ved i arrays, de ikke går op til n, de går op til n minus 1. 867 00:47:09,570 --> 00:47:11,110 Så vi har nogle grænser i vores array. 868 00:47:11,110 --> 00:47:15,730 Og disse indledende grænser tilfældigvis de oprindelige grænser for vores problem. 869 00:47:15,730 --> 00:47:16,640 OK. 870 00:47:16,640 --> 00:47:19,200 Så det lyder godt. 871 00:47:19,200 --> 00:47:22,380 Så hvis vi går tilbage til denne linje, mens længden af ​​listen er større end 0, 872 00:47:22,380 --> 00:47:24,752 hvad stedet for n, bør vi sætter i her? 873 00:47:24,752 --> 00:47:28,820 >> STUDENT: Skriv slutter minus begyndelsen. 874 00:47:28,820 --> 00:47:34,780 >> JASON HIRSCHHORN: Mens slutter minus begynder er større end 0? 875 00:47:34,780 --> 00:47:35,480 OK. 876 00:47:35,480 --> 00:47:37,730 Og vi kunne, hvis vi ønskede at gøre, at en lidt pænere, hvad 877 00:47:37,730 --> 00:47:38,980 ellers kunne vi gøre? 878 00:47:38,980 --> 00:47:41,650 879 00:47:41,650 --> 00:47:43,412 Hvis vi ønskede at rense denne kode lidt op? 880 00:47:43,412 --> 00:47:46,716 881 00:47:46,716 --> 00:47:48,180 Hvordan kan vi slippe af med 0? 882 00:47:48,180 --> 00:47:51,560 883 00:47:51,560 --> 00:47:52,690 Dette er blot en stil spørgsmål. 884 00:47:52,690 --> 00:47:53,690 Det er korrekt, lige nu. 885 00:47:53,690 --> 00:47:54,870 >> STUDENT: Afslutning ikke lige begyndelse? 886 00:47:54,870 --> 00:47:55,740 >> JASON HIRSCHHORN: Vi kan gøre hvad? 887 00:47:55,740 --> 00:47:56,730 >> [indskyde STEMMER] 888 00:47:56,730 --> 00:47:57,330 >> STUDENT: Ending er større? 889 00:47:57,330 --> 00:47:57,720 >> JASON HIRSCHHORN: Ja. 890 00:47:57,720 --> 00:48:01,110 Vi kan bare gøre, mens slutter er større end begyndelsen. 891 00:48:01,110 --> 00:48:03,580 Right. 892 00:48:03,580 --> 00:48:06,240 Vi har tilføjet begyndt til den anden side af det, og vi sluppet af 0. 893 00:48:06,240 --> 00:48:08,000 Så dette ser bare en lidt renere. 894 00:48:08,000 --> 00:48:08,990 OK. 895 00:48:08,990 --> 00:48:11,460 Så mens længden af ​​listen er 0, skrev vi at mens slutter, er større 896 00:48:11,460 --> 00:48:12,240 end begyndelsen. 897 00:48:12,240 --> 00:48:19,840 Vi kommer til at sætte i vores nødvendig krøllede parenteser, og derefter den første ting 898 00:48:19,840 --> 00:48:22,090 vi ønsker at gøre, er at se på dem i en lille liste. 899 00:48:22,090 --> 00:48:22,510 Dig? 900 00:48:22,510 --> 00:48:23,320 Kan du give mig det - 901 00:48:23,320 --> 00:48:26,460 >> STUDENT: Hvis parentes værdi firkantet beslag - 902 00:48:26,460 --> 00:48:30,450 >> JASON HIRSCHHORN: Hvis parentes værdi firkantet beslag. 903 00:48:30,450 --> 00:48:33,210 >> STUDENT: Ending divideres med 2. 904 00:48:33,210 --> 00:48:33,952 >> JASON HIRSCHHORN: Ending? 905 00:48:33,952 --> 00:48:35,280 >> STUDENT: Jeg ser et problem med din - 906 00:48:35,280 --> 00:48:35,750 >> JASON HIRSCHHORN: OK. 907 00:48:35,750 --> 00:48:39,150 Tja, se på midten. 908 00:48:39,150 --> 00:48:41,226 Hvordan kan vi vide, hvad den midterste er? 909 00:48:41,226 --> 00:48:42,450 Ja. 910 00:48:42,450 --> 00:48:43,070 Så lad mig slette denne kode. 911 00:48:43,070 --> 00:48:46,360 Hvordan kan vi vide, hvad den midterste er? 912 00:48:46,360 --> 00:48:48,003 I noget, når du har begyndelsen og enden, hvordan kan du finde 913 00:48:48,003 --> 00:48:48,876 midten? 914 00:48:48,876 --> 00:48:49,590 >> STUDENT: Du gennemsnittet. 915 00:48:49,590 --> 00:48:51,820 >> STUDENT: Du tilføjer dem sammen og derefter - 916 00:48:51,820 --> 00:48:53,150 >> JASON HIRSCHHORN: Tilføj dem sammen og derefter? 917 00:48:53,150 --> 00:48:54,090 >> STUDENT: Og du gennemsnittet. 918 00:48:54,090 --> 00:48:55,050 Dividere det med 2.. 919 00:48:55,050 --> 00:48:56,500 >> JASON HIRSCHHORN: Tilføj dem sammen og dividere med 2.. 920 00:48:56,500 --> 00:48:59,400 Så int midterste lig? 921 00:48:59,400 --> 00:49:01,120 Tom, kan du give mig det? 922 00:49:01,120 --> 00:49:03,550 >> STUDENT: Begyndelsen plus slutter - 923 00:49:03,550 --> 00:49:04,950 >> JASON HIRSCHHORN: Begyndelsen plus slutter. 924 00:49:04,950 --> 00:49:06,880 >> STUDENT: Alle, beslag, divideret med 2.. 925 00:49:06,880 --> 00:49:10,940 >> JASON HIRSCHHORN: Alle, i parentes, divideret med to. 926 00:49:10,940 --> 00:49:16,300 Så det giver mig den midterste af noget, korrekt? 927 00:49:16,300 --> 00:49:18,980 >> STUDENT: Du skal også til at runde det op. 928 00:49:18,980 --> 00:49:19,990 >> JASON HIRSCHHORN: Hvad gør du mener, jeg har brug for at runde det op? 929 00:49:19,990 --> 00:49:20,400 >> [indskyde STEMMER] 930 00:49:20,400 --> 00:49:24,520 >> STUDENT: Fordi hvis det er et ulige nummer, så er det ligesom - 931 00:49:24,520 --> 00:49:25,440 >> JASON HIRSCHHORN: Nå, OK. 932 00:49:25,440 --> 00:49:26,360 Så jeg kunne runde det op. 933 00:49:26,360 --> 00:49:33,350 Men hvis det er et ulige antal, 5, kan jeg idet 1 væk fra midten. 934 00:49:33,350 --> 00:49:35,665 Eller hvis det er et lige tal, snarere der er en bedre sag. 935 00:49:35,665 --> 00:49:39,600 Hvis det er 4, har vi kun 4, kan jeg tage den første "midten", citat, citat slut eller 936 00:49:39,600 --> 00:49:41,760 den anden "midten" en. 937 00:49:41,760 --> 00:49:46,390 Enten ville arbejde for en binær søgning, så jeg behøver faktisk ikke at runde det. 938 00:49:46,390 --> 00:49:48,640 Men der er en anden ting, jeg nødt til at se på denne linje. 939 00:49:48,640 --> 00:49:50,530 Vi er måske ikke klar over det endnu, men vi vil vende tilbage til det. 940 00:49:50,530 --> 00:49:53,200 Da denne linje faktisk stadig brug en anden ting. 941 00:49:53,200 --> 00:49:55,990 >> Men indtil videre har vi skrevet fire linjer kode. 942 00:49:55,990 --> 00:49:58,120 Vi har fået vores start og slutter markører. 943 00:49:58,120 --> 00:50:01,320 Vi har vores while-løkke, der kortlægger på direkte til vores pseudokode. 944 00:50:01,320 --> 00:50:05,790 Vi kigger på midten, der kortlægger direkte på vores pseudokode. 945 00:50:05,790 --> 00:50:09,070 Jeg vil sige dette går til midten af listen, denne linje kode. 946 00:50:09,070 --> 00:50:11,560 Og så, når vi går til midten af listen, den næste ting, vi skal gøre 947 00:50:11,560 --> 00:50:14,880 er kontrollere, om vores værdi er der for pseudokoden vi skrev tidligere. 948 00:50:14,880 --> 00:50:17,100 >> Så hvordan kan vi kontrollere, om vores værdi er midten af ​​listen? 949 00:50:17,100 --> 00:50:17,300 Dig. 950 00:50:17,300 --> 00:50:18,511 Hvorfor kan du ikke gøre det? 951 00:50:18,511 --> 00:50:23,070 >> STUDENT: Hvis vores værdi er er på midten er lig med 952 00:50:23,070 --> 00:50:24,592 hvad vi indstiller - 953 00:50:24,592 --> 00:50:26,190 Jeg mener lige lig - 954 00:50:26,190 --> 00:50:26,690 >> JASON HIRSCHHORN: It - 955 00:50:26,690 --> 00:50:27,940 OK. 956 00:50:27,940 --> 00:50:30,080 957 00:50:30,080 --> 00:50:32,170 >> STUDENT: Jeg er ikke sikker på, hvad variabel vi leder 958 00:50:32,170 --> 00:50:32,850 for selv om, er, fordi - 959 00:50:32,850 --> 00:50:33,330 >> [indskyde STEMMER] 960 00:50:33,330 --> 00:50:34,520 >> STUDENT: [uhørligt]. 961 00:50:34,520 --> 00:50:35,060 >> JASON HIRSCHHORN: Præcis. 962 00:50:35,060 --> 00:50:37,260 Per funktionen erklæring, vi leder efter en værdi. 963 00:50:37,260 --> 00:50:39,760 Så vi søger efter en værdi i en vifte af værdier. 964 00:50:39,760 --> 00:50:41,080 Så du er helt rigtigt. 965 00:50:41,080 --> 00:50:45,040 Du vil gøre, hvis den er åben parentes værdi beslag midten lukket beslag ligemænd 966 00:50:45,040 --> 00:50:49,930 lig værdi, og inde er der hvad skal vi gøre? 967 00:50:49,930 --> 00:50:51,230 Hvis vores værdi er der, hvad skal vi gøre? 968 00:50:51,230 --> 00:50:51,420 >> [indskyde STEMMER] 969 00:50:51,420 --> 00:50:52,160 >> STUDENT: Tilbage nul. 970 00:50:52,160 --> 00:50:53,070 >> JASON HIRSCHHORN: Return sandt. 971 00:50:53,070 --> 00:50:54,790 >> STUDENT: Return sandt. 972 00:50:54,790 --> 00:50:57,856 >> JASON HIRSCHHORN: Michael, hvad betyder denne linje gøre? 973 00:50:57,856 --> 00:51:01,105 >> STUDENT: [uhørligt] programmet har kørt dens forløb, og der er over, og 974 00:51:01,105 --> 00:51:01,920 du har, hvad du skal gøre? 975 00:51:01,920 --> 00:51:03,030 >> JASON HIRSCHHORN: Programmet eller hvad? 976 00:51:03,030 --> 00:51:03,700 I dette tilfælde? 977 00:51:03,700 --> 00:51:04,210 >> STUDENT: Den funktion. 978 00:51:04,210 --> 00:51:05,170 >> JASON HIRSCHHORN: Den funktion. 979 00:51:05,170 --> 00:51:08,420 Og så for at vende tilbage til, hvad der kaldes det og give det den værdi, sandt. 980 00:51:08,420 --> 00:51:09,890 Præcis højre. 981 00:51:09,890 --> 00:51:10,170 Main. 982 00:51:10,170 --> 00:51:12,035 Hvad er returtypen af hoved, Michael? 983 00:51:12,035 --> 00:51:16,480 984 00:51:16,480 --> 00:51:17,150 >> STUDENT: int, heltal? 985 00:51:17,150 --> 00:51:18,080 >> JASON HIRSCHHORN: int, nøjagtigt. 986 00:51:18,080 --> 00:51:18,680 Et heltal. 987 00:51:18,680 --> 00:51:20,980 Det var bare et spørgsmål for at sikre, du fyre har været på toppen af ​​det. 988 00:51:20,980 --> 00:51:24,250 Hvad betyder det normalt vender tilbage, hvis alle tingene fungerer godt? 989 00:51:24,250 --> 00:51:24,520 >> STUDENT: Zero. 990 00:51:24,520 --> 00:51:24,820 >> JASON HIRSCHHORN: Zero. 991 00:51:24,820 --> 00:51:25,430 Præcis højre. 992 00:51:25,430 --> 00:51:28,790 >> STUDENT: Hvis det bare returnerer true, der er ingen oplysninger bliver givet 993 00:51:28,790 --> 00:51:30,675 om hvad - 994 00:51:30,675 --> 00:51:34,040 Åh, er det bare at sige, at der værdi der er inde i array. 995 00:51:34,040 --> 00:51:35,350 >> JASON HIRSCHHORN: Præcis. 996 00:51:35,350 --> 00:51:38,080 Dette program er ikke at give oplysninger hvor nøjagtig værdi. 997 00:51:38,080 --> 00:51:41,850 Det er kun at sige, ja, vi fandt det, eller nej, vi ikke finde det. 998 00:51:41,850 --> 00:51:42,990 Så hvis nummer findes, returnere sandt. 999 00:51:42,990 --> 00:51:45,500 Tja, faktisk vi bare gjorde det rigtig hurtigt med at en linje kode. 1000 00:51:45,500 --> 00:51:47,500 Så jeg vil flytte denne linje af pseudokode. 1001 00:51:47,500 --> 00:51:50,045 >> STUDENT: Har vi ikke brug for at ændre array? 1002 00:51:50,045 --> 00:51:52,830 Det bør være værdier, ikke værdi, right? 1003 00:51:52,830 --> 00:51:53,430 >> JASON HIRSCHHORN: Undskyld. 1004 00:51:53,430 --> 00:51:54,010 Tak. 1005 00:51:54,010 --> 00:51:54,800 >> STUDENT: Ja. 1006 00:51:54,800 --> 00:51:55,850 >> JASON HIRSCHHORN: Denne linje bør være værdier. 1007 00:51:55,850 --> 00:51:57,150 Præcis højre. 1008 00:51:57,150 --> 00:51:57,920 OK. 1009 00:51:57,920 --> 00:51:59,170 Så vi har kigget på den midterste liste. 1010 00:51:59,170 --> 00:52:00,790 Hvis antallet fundet afkast sandt. 1011 00:52:00,790 --> 00:52:04,470 Fortsætter med vores pseudokode, hvis midten er større, søg venstre. 1012 00:52:04,470 --> 00:52:09,640 Så jeg havde i her, hvis nummer højere, søg venstre. 1013 00:52:09,640 --> 00:52:12,700 1014 00:52:12,700 --> 00:52:14,462 Konstantin, kan du give mig denne linje kode? 1015 00:52:14,462 --> 00:52:17,240 1016 00:52:17,240 --> 00:52:23,520 >> STUDENT: Hvis værdien af ​​midten - 1017 00:52:23,520 --> 00:52:24,890 >> JASON HIRSCHHORN: Så hvis værdi - 1018 00:52:24,890 --> 00:52:28,890 hvis åben parantes værdier beslag midterste close beslag - 1019 00:52:28,890 --> 00:52:31,500 >> STUDENT: Er mindre end værdi? 1020 00:52:31,500 --> 00:52:32,760 >> JASON HIRSCHHORN: Er mindre end. 1021 00:52:32,760 --> 00:52:33,800 >> STUDENT: Mindre end værdi. 1022 00:52:33,800 --> 00:52:34,060 >> JASON HIRSCHHORN: Værdi. 1023 00:52:34,060 --> 00:52:35,310 Tja, faktisk, du ønsker at kontrollere, om nummeret - 1024 00:52:35,310 --> 00:52:38,310 1025 00:52:38,310 --> 00:52:38,490 Undskyld. 1026 00:52:38,490 --> 00:52:39,140 Det er lidt forvirrende. 1027 00:52:39,140 --> 00:52:43,920 Men ellers hvis antallet i midten af ​​listen er større. 1028 00:52:43,920 --> 00:52:45,170 >> STUDENT: Åh, OK. 1029 00:52:45,170 --> 00:52:49,800 1030 00:52:49,800 --> 00:52:50,410 >> JASON HIRSCHHORN: Jeg vil ændre det. 1031 00:52:50,410 --> 00:52:55,060 Else hvis midten er højere, vi vil søge venstre, OK? 1032 00:52:55,060 --> 00:52:57,310 Og hvad gør vi inde dette, hvis tilstand? 1033 00:52:57,310 --> 00:53:03,660 1034 00:53:03,660 --> 00:53:07,510 >> STUDENT: Kan jeg lave en lille ændring i den tilstand, ændre det til andet, hvis? 1035 00:53:07,510 --> 00:53:08,380 >> JASON HIRSCHHORN: Else nu hvis? 1036 00:53:08,380 --> 00:53:09,270 OK. 1037 00:53:09,270 --> 00:53:12,840 Så denne kode vil køre om det samme. 1038 00:53:12,840 --> 00:53:18,620 Men det gode ved at bruge, hvis ellers hvis ellers hvis eller hvis ellers hvis ellers 1039 00:53:18,620 --> 00:53:22,320 betyder, at kun en af ​​dem kommer til at skal kontrolleres, ikke alle tre af dem, 1040 00:53:22,320 --> 00:53:23,290 potentielt. 1041 00:53:23,290 --> 00:53:25,530 Og det gør det en lille smule pænere på den computer, der er 1042 00:53:25,530 --> 00:53:26,670 kører dit program. 1043 00:53:26,670 --> 00:53:27,620 >> Så [? Konstantin,?] 1044 00:53:27,620 --> 00:53:31,330 Vi er inde i denne linje, ellers hvis værdier beslag midten luk beslag 1045 00:53:31,330 --> 00:53:32,260 er større end værdi. 1046 00:53:32,260 --> 00:53:33,150 Hvad skal vi gøre? 1047 00:53:33,150 --> 00:53:33,970 Vi har brug for at søge venstre. 1048 00:53:33,970 --> 00:53:35,220 Hvordan gør vi det? 1049 00:53:35,220 --> 00:53:46,960 1050 00:53:46,960 --> 00:53:48,720 Jeg har tænkt mig at give dig en start. 1051 00:53:48,720 --> 00:53:52,210 >> Vi har disse to ting kaldet begynder og slutter. 1052 00:53:52,210 --> 00:53:57,340 Så hvad der skal ske til begyndelsen? 1053 00:53:57,340 --> 00:53:59,640 Hvis du ønsker at søge venstre for liste, vi får vores nuværende begyndelsen. 1054 00:53:59,640 --> 00:54:01,080 Hvad skal vi gøre det? 1055 00:54:01,080 --> 00:54:04,220 >> STUDENT: Vi sætter begyndelsen til midten plus 1. 1056 00:54:04,220 --> 00:54:05,120 >> JASON HIRSCHHORN: Så hvis vi er søge på venstre? 1057 00:54:05,120 --> 00:54:06,250 >> STUDENT: Beklager, midterste minus - 1058 00:54:06,250 --> 00:54:11,310 så slutningen ville være midten minus 1 og begyndelsen - 1059 00:54:11,310 --> 00:54:12,450 >> JASON HIRSCHHORN: Og hvad sker til begyndelsen? 1060 00:54:12,450 --> 00:54:13,210 >> STUDENT: Det forbliver den samme. 1061 00:54:13,210 --> 00:54:14,120 >> JASON HIRSCHHORN: Så betydning forbliver den samme. 1062 00:54:14,120 --> 00:54:16,040 Hvis vi søger til venstre, er vi anvendelse af den samme begyndelse - 1063 00:54:16,040 --> 00:54:16,860 helt rigtigt. 1064 00:54:16,860 --> 00:54:17,870 Og det slutter? 1065 00:54:17,870 --> 00:54:19,390 Undskyld, hvad gør slutter lige igen? 1066 00:54:19,390 --> 00:54:20,750 >> STUDENT: Middle minus 1. 1067 00:54:20,750 --> 00:54:21,620 >> JASON HIRSCHHORN: Middle minus 1. 1068 00:54:21,620 --> 00:54:23,470 Nu, hvorfor minus 1, ikke bare midten? 1069 00:54:23,470 --> 00:54:32,870 1070 00:54:32,870 --> 00:54:35,570 >> STUDENT: Den midterste er ude af billedet allerede, fordi vi havde 1071 00:54:35,570 --> 00:54:36,700 kontrolleret, at det er ude? 1072 00:54:36,700 --> 00:54:37,630 >> JASON HIRSCHHORN: Det er helt rigtigt. 1073 00:54:37,630 --> 00:54:38,580 Midten er ude af billedet. 1074 00:54:38,580 --> 00:54:39,800 Vi har allerede tjekket midten. 1075 00:54:39,800 --> 00:54:44,730 Så vi ønsker ikke "i midten", citat citat slut, at fortsætte med at være i 1076 00:54:44,730 --> 00:54:46,110 array, vi leder. 1077 00:54:46,110 --> 00:54:47,670 Så det er fantastisk. 1078 00:54:47,670 --> 00:54:50,670 >> Else hvis værdier beslag midten er større end værdien slutter ligemænd 1079 00:54:50,670 --> 00:54:51,920 midterste minus 1. 1080 00:54:51,920 --> 00:54:55,060 1081 00:54:55,060 --> 00:54:57,340 Jeff, hvad med denne sidste linje? 1082 00:54:57,340 --> 00:54:58,590 >> STUDENT: Else. 1083 00:54:58,590 --> 00:55:02,486 1084 00:55:02,486 --> 00:55:06,000 Værdier midten er mindre end værdi? 1085 00:55:06,000 --> 00:55:07,570 >> JASON HIRSCHHORN: Vi vil du giver mig andet. 1086 00:55:07,570 --> 00:55:09,310 Så hvis du ikke giver mig - 1087 00:55:09,310 --> 00:55:12,270 >> STUDENT: Så begynder ville være midten plus 1. 1088 00:55:12,270 --> 00:55:16,100 1089 00:55:16,100 --> 00:55:19,070 >> JASON Hirschhorn: Begyndelsen ligemænd midten plus 1 igen for den samme 1090 00:55:19,070 --> 00:55:20,820 grunden til, at Constantine gav os tidligere. 1091 00:55:20,820 --> 00:55:24,280 Og til sidst, er der ikke givet mig en linje kode endnu? 1092 00:55:24,280 --> 00:55:26,600 Return false, Aleha, hvad vi skriver her? 1093 00:55:26,600 --> 00:55:28,590 >> STUDENT: Tilbage falsk. 1094 00:55:28,590 --> 00:55:29,320 >> JASON HIRSCHHORN: Tilbage falsk. 1095 00:55:29,320 --> 00:55:33,340 Og vi har brug for at gøre det, for hvis vi finder det ikke, er vi nødt til at sige, at vi 1096 00:55:33,340 --> 00:55:34,080 kunne ikke finde det. 1097 00:55:34,080 --> 00:55:36,270 Og vi sagde, at vi kommer til at returnere en bool, så vi helt sikkert nødt til at vende tilbage 1098 00:55:36,270 --> 00:55:38,150 en bool et eller andet sted. 1099 00:55:38,150 --> 00:55:42,590 >> Så lad os køre denne kode. 1100 00:55:42,590 --> 00:55:44,520 Jeg er faktisk at gå til - 1101 00:55:44,520 --> 00:55:45,930 så vi er i terminalen. 1102 00:55:45,930 --> 00:55:47,230 Vi vil rydde vores vindue. 1103 00:55:47,230 --> 00:55:49,270 Lad os gøre hele. 1104 00:55:49,270 --> 00:55:50,340 Vi fandt der er en fejl. 1105 00:55:50,340 --> 00:55:54,280 Der er en fejl på linje 15, der forventes semikolon ved udgangen af 1106 00:55:54,280 --> 00:55:54,890 erklæring. 1107 00:55:54,890 --> 00:55:56,454 Så hvad gjorde jeg glemme? 1108 00:55:56,454 --> 00:55:57,230 >> STUDENT: semikolon. 1109 00:55:57,230 --> 00:56:00,200 >> JASON HIRSCHHORN: Semikolon lige heroppe. 1110 00:56:00,200 --> 00:56:00,950 Jeg tror, ​​det var Toms kode. 1111 00:56:00,950 --> 00:56:01,870 Så Tom, [uhørligt]. 1112 00:56:01,870 --> 00:56:03,120 Just kidding. 1113 00:56:03,120 --> 00:56:05,010 1114 00:56:05,010 --> 00:56:07,310 Lad os gør alt igen. 1115 00:56:07,310 --> 00:56:10,180 >> STUDENT: Hvad Dropbox mappe bør vi være i til dette? 1116 00:56:10,180 --> 00:56:11,345 >> JASON HIRSCHHORN: Så du kan bare se for denne bit. 1117 00:56:11,345 --> 00:56:16,380 Men igen, hvis du ønsker at flytte denne kode i din pset3 mappe til prøve 1118 00:56:16,380 --> 00:56:17,050 det ud, det er, hvad jeg gjorde. 1119 00:56:17,050 --> 00:56:18,600 Hvis du lægger mærke til her - undskyld, godt spørgsmål. 1120 00:56:18,600 --> 00:56:19,460 >> [? LS,?] 1121 00:56:19,460 --> 00:56:24,700 Jeg har i her find.c kode fra denne uges distro kode. 1122 00:56:24,700 --> 00:56:26,300 Jeg har helpers.h. 1123 00:56:26,300 --> 00:56:30,010 Jeg har en Make-fil, som jeg faktisk redigeret en smule til også at omfatte disse nye 1124 00:56:30,010 --> 00:56:30,710 filer, vi skriver. 1125 00:56:30,710 --> 00:56:34,120 Alt dette kodeks vil være til rådighed, ikke fordelingen kode, men den nye 1126 00:56:34,120 --> 00:56:39,510 Gør fil, den nye helpers.h filen være tilgængelige online til download. 1127 00:56:39,510 --> 00:56:41,800 Igen, så det er de ekstra koder, vi har. 1128 00:56:41,800 --> 00:56:46,130 >> Så gør alt, pr denne linie gør finde, binær, boble valg - gør 1129 00:56:46,130 --> 00:56:50,930 alle tre af dem og samler ind denne eksekverbar kode fund. 1130 00:56:50,930 --> 00:56:54,090 Så generelt, ønsker vi ikke til lige til check50. 1131 00:56:54,090 --> 00:56:57,580 Vi ønsker at køre nogle tests på vores egen. 1132 00:56:57,580 --> 00:57:11,750 Men lige så vi kan fremskynde det en smule, check50 2013 pset3.find vil passere 1133 00:57:11,750 --> 00:57:14,630 i helpers.c-- mit dårlige. 1134 00:57:14,630 --> 00:57:16,050 >> Jeg har ikke lige nu. 1135 00:57:16,050 --> 00:57:20,670 Så vi faktisk kommer til at køre koden for alvor. 1136 00:57:20,670 --> 00:57:23,570 Usage.find /, ved du hvad det betyder? 1137 00:57:23,570 --> 00:57:25,970 >> STUDENT: Du har brug for en anden kommandolinjen på det. 1138 00:57:25,970 --> 00:57:26,980 >> JASON HIRSCHHORN: Jeg har brug for en anden kommandolinje. 1139 00:57:26,980 --> 00:57:30,640 Og pr specifikationen, jeg har brug for at indtaste, hvad vi leder efter. 1140 00:57:30,640 --> 00:57:33,750 Så lad os se efter 42. 1141 00:57:33,750 --> 00:57:37,030 Vi vil holde det i sorterede, fordi vi har ikke skrevet en slags funktion endnu - 1142 00:57:37,030 --> 00:57:41,830 42, 43, 44. 1143 00:57:41,830 --> 00:57:46,240 >> Og Kontrol D ikke fandt nål i en høstak. 1144 00:57:46,240 --> 00:57:46,505 Det er dårlige. 1145 00:57:46,505 --> 00:57:47,200 Det er helt sikkert der. 1146 00:57:47,200 --> 00:57:48,090 Lad os prøve noget andet. 1147 00:57:48,090 --> 00:57:49,860 Måske er det fordi jeg sætter det i begyndelsen. 1148 00:57:49,860 --> 00:57:54,490 >> Lad os gøre 41, 42, 43. 1149 00:57:54,490 --> 00:57:55,012 Der vi går. 1150 00:57:55,012 --> 00:57:56,400 Den fandt det. 1151 00:57:56,400 --> 00:58:00,040 Lad os sætte det i slutningen nu, bare så vi kan være grundig - 1152 00:58:00,040 --> 00:58:03,580 40, 41, 42. 1153 00:58:03,580 --> 00:58:05,760 Fandt du ikke finde nålen. 1154 00:58:05,760 --> 00:58:07,550 Så jeg nævnte dette tidligere. 1155 00:58:07,550 --> 00:58:08,980 Desværre, jeg vidste dette skulle ske. 1156 00:58:08,980 --> 00:58:11,490 >> Men for pædagogiske formål, det er godt at udforske det. 1157 00:58:11,490 --> 00:58:12,990 Det fungerer ikke. 1158 00:58:12,990 --> 00:58:16,020 Af en eller anden grund, kan den ikke finde den. 1159 00:58:16,020 --> 00:58:18,970 Vi ved, hvad der er derinde, men vi ikke finde det. 1160 00:58:18,970 --> 00:58:24,140 Så én ting, vi kan gøre, er at gå igennem GDB at finde det, men gør nogen, 1161 00:58:24,140 --> 00:58:27,850 uden at gå gennem GDB, har en fornemmelse af, hvor vi skruet op? 1162 00:58:27,850 --> 00:58:28,480 [? Madu? ?] 1163 00:58:28,480 --> 00:58:30,960 >> STUDENT: Jeg tror, ​​det kan være, når slutter er lig med begyndelsen, og det er 1164 00:58:30,960 --> 00:58:33,090 blot en en-element listen. 1165 00:58:33,090 --> 00:58:35,560 Så er det bare ignorerer det i stedet for faktisk at kontrollere det. 1166 00:58:35,560 --> 00:58:36,940 >> JASON HIRSCHHORN: Det er helt rigtigt. 1167 00:58:36,940 --> 00:58:41,110 Når slutning lig begyndelsen, gør vi stadig har et element i vores liste? 1168 00:58:41,110 --> 00:58:42,480 >> STUDENT: Ja. 1169 00:58:42,480 --> 00:58:45,450 >> JASON HIRSCHHORN: Ja, i virkeligheden, vi har én og kun ét element. 1170 00:58:45,450 --> 00:58:50,500 Og det vil sandsynligvis ske, når, per den kode, vi testede, vi er ved 1171 00:58:50,500 --> 00:58:54,640 foran høstak eller slutningen af ​​høstak. 1172 00:58:54,640 --> 00:58:56,000 Det er, hvor begyndelsen og slutning kommer til at lige 1173 00:58:56,000 --> 00:58:57,820 en, med binær søgning. 1174 00:58:57,820 --> 00:59:01,440 Så i disse to tilfælde er det ikke virkede, fordi slutter var lig med begyndelsen. 1175 00:59:01,440 --> 00:59:06,030 >> Men hvis slutter er lig med starten betyder dette, mens løkken udføre? 1176 00:59:06,030 --> 00:59:06,390 Det gør det ikke. 1177 00:59:06,390 --> 00:59:08,660 Og vi kunne have kontrolleret der igen gennem GDB. 1178 00:59:08,660 --> 00:59:14,000 Så hvordan kan vi løse denne kode, fordi når mens slutter er lig med 1179 00:59:14,000 --> 00:59:16,070 begynder, vil vi også dette mens løkken til at køre. 1180 00:59:16,070 --> 00:59:18,620 >> Så hvad fix kan vi gøre til linje 18? 1181 00:59:18,620 --> 00:59:21,060 >> STUDENT: [uhørligt] er større end eller lig med. 1182 00:59:21,060 --> 00:59:21,700 >> JASON HIRSCHHORN: Præcis højre. 1183 00:59:21,700 --> 00:59:24,600 Mens slutningen er større end eller lig med begyndelsen. 1184 00:59:24,600 --> 00:59:27,300 Så nu, vi sørge for at få det hjørne tilfældet i slutningen. 1185 00:59:27,300 --> 00:59:27,870 Og lad os se. 1186 00:59:27,870 --> 00:59:29,560 Lad os køre dette endnu en gang. 1187 00:59:29,560 --> 00:59:31,266 >> Lad os gøre alle. 1188 00:59:31,266 --> 00:59:33,910 Igen, er du nødt til bare følge med her. 1189 00:59:33,910 --> 00:59:36,280 Find 41 denne gang. 1190 00:59:36,280 --> 00:59:37,360 Bare holde det konsekvent. 1191 00:59:37,360 --> 00:59:38,210 >> Find 42. 1192 00:59:38,210 --> 00:59:38,930 Lad os sige det i starten - 1193 00:59:38,930 --> 00:59:41,630 42, 43, 44. 1194 00:59:41,630 --> 00:59:42,860 Vi fandt det. 1195 00:59:42,860 --> 00:59:47,710 Så det var faktisk ændringen vi skulle gøre. 1196 00:59:47,710 --> 00:59:51,090 >> Det var en masse kodning vi lige gjorde, binær søgning. 1197 00:59:51,090 --> 00:59:55,760 Er der nogen har nogen spørgsmål, før Jeg flytter på i linjer, vi skrev i 1198 00:59:55,760 --> 00:59:58,750 binær søgning eller hvordan vi regnede ud af, hvad vi regne ud? 1199 00:59:58,750 --> 01:00:01,900 1200 01:00:01,900 --> 01:00:06,270 Før vi går videre, vil jeg også gerne påpege ud af, at store og hele, vi kortlagt 1201 01:00:06,270 --> 01:00:09,300 vores pseudokode en til én på vores kode. 1202 01:00:09,300 --> 01:00:11,550 >> Vi havde det tricky ting at finde ud af med det 1203 01:00:11,550 --> 01:00:12,890 begynder og slutter. 1204 01:00:12,890 --> 01:00:17,380 Men havde du ikke regnet det ud, du ville have skrevet temmelig 1205 01:00:17,380 --> 01:00:20,740 identisk kode, bortset disse top to linjer. 1206 01:00:20,740 --> 01:00:23,380 Og så ville du have indset, når du gjorde det i kontrol og sager, 1207 01:00:23,380 --> 01:00:24,840 du har brug for noget andet. 1208 01:00:24,840 --> 01:00:28,510 Så selv hvis du havde fulgt vores pseudo-kode linje for linje, ville du har 1209 01:00:28,510 --> 01:00:31,130 fået alle men to linjer af kode, du havde brug for at skrive. 1210 01:00:31,130 --> 01:00:33,900 >> Og jeg ville være villig til at vædde på, at du fyre ville have alt regnet det ud 1211 01:00:33,900 --> 01:00:37,940 temmelig hurtigt, at du havde brug for at sætte en slags markør i der at regne 1212 01:00:37,940 --> 01:00:39,190 ud af, hvor du var. 1213 01:00:39,190 --> 01:00:41,540 1214 01:00:41,540 --> 01:00:44,550 Det igen, er kraften i at gøre pseudo-kode i forvejen. 1215 01:00:44,550 --> 01:00:47,310 Så vi kan gøre logikken først, og derefter vi kan bekymre sig om syntaks. 1216 01:00:47,310 --> 01:00:51,470 >> Havde vi været forvirret over logikken mens du prøver at skrive denne kode i C, 1217 01:00:51,470 --> 01:00:53,110 vi ville have fået alle rodet op. 1218 01:00:53,110 --> 01:00:56,340 Og så ville vi være stille spørgsmål om logik og syntaks og meshing 1219 01:00:56,340 --> 01:00:57,320 dem alle sammen. 1220 01:00:57,320 --> 01:01:02,170 Og vi ville have fået tabt i, hvad der kan hurtigt blive en 1221 01:01:02,170 --> 01:01:04,000 meget vanskeligt problem. 1222 01:01:04,000 --> 01:01:08,680 Så lad os gå videre nu til valg slags. 1223 01:01:08,680 --> 01:01:10,760 >> Vi har 20 minutter tilbage. 1224 01:01:10,760 --> 01:01:14,130 Så jeg har en fornemmelse af, vi vil ikke være i stand til at komme igennem alle valg slags 1225 01:01:14,130 --> 01:01:15,940 og boble slags. 1226 01:01:15,940 --> 01:01:20,670 Men lad os i det mindste forsøg for at afslutte valget slags. 1227 01:01:20,670 --> 01:01:23,540 Så gennemføre valget sortere ved hjælp af følgende funktion erklæring. 1228 01:01:23,540 --> 01:01:27,530 >> Også denne taget fra problem sæt specifikationer. 1229 01:01:27,530 --> 01:01:31,560 Int værdier parenteser, er et array af heltal. 1230 01:01:31,560 --> 01:01:33,490 Og int.n er størrelsen af ​​denne array. 1231 01:01:33,490 --> 01:01:36,840 Valg slags går at sortere dette array. 1232 01:01:36,840 --> 01:01:43,580 >> Så per vores mentale model for udvælgelse sortere, vi trækker - 1233 01:01:43,580 --> 01:01:47,720 første, vi går gennem listen den første tid, finde det mindste tal, 1234 01:01:47,720 --> 01:01:52,860 sætte det i starten, finde den anden mindste tal, sætte det i 1235 01:01:52,860 --> 01:01:56,380 anden position, hvis vi ønsker at sortere i stigende rækkefølge. 1236 01:01:56,380 --> 01:01:58,440 Jeg er ikke tvinger dig til at skrive pseudo-kode lige nu. 1237 01:01:58,440 --> 01:02:01,350 >> Men før vi gør koden som en klasse i fem minutter, vi kommer til at skrive 1238 01:02:01,350 --> 01:02:03,550 pseudo-kode, så vi har nogle fornuft af hvor vi skal hen. 1239 01:02:03,550 --> 01:02:05,630 Så forsøge at skrive pseudo-kode på din egen. 1240 01:02:05,630 --> 01:02:08,610 Og derefter forsøge at slå denne pseudo-kode i kode. 1241 01:02:08,610 --> 01:02:10,740 Vi vil gøre det som en gruppe fem minutter. 1242 01:02:10,740 --> 01:02:32,560 1243 01:02:32,560 --> 01:02:33,895 >> Og selvfølgelig, så lad mig vide, hvis du har spørgsmål. 1244 01:02:33,895 --> 01:03:56,738 1245 01:03:56,738 --> 01:03:58,230 >> STUDENT: At det? 1246 01:03:58,230 --> 01:04:00,280 >> JASON HIRSCHHORN: Se hvor langt du kan komme i yderligere to minutter. 1247 01:04:00,280 --> 01:04:01,790 Jeg forstår dig ikke vil være i stand til at afslutte. 1248 01:04:01,790 --> 01:04:03,050 Men vi vil gå over dette som en gruppe. 1249 01:04:03,050 --> 01:04:57,830 1250 01:04:57,830 --> 01:05:00,630 >> Du er al kodning så [uhørligt], så jeg er ked af at holde pause, hvad du laver. 1251 01:05:00,630 --> 01:05:02,530 Men lad os gå igennem dette som en gruppe. 1252 01:05:02,530 --> 01:05:07,590 Og igen, binær søgning, du alle give mig en, hvis ikke flere linjer kode. 1253 01:05:07,590 --> 01:05:08,530 Tak for det. 1254 01:05:08,530 --> 01:05:11,730 Vi kommer til at gøre det samme her, kode sammen som en gruppe. 1255 01:05:11,730 --> 01:05:15,170 >> Så valg slags - lad os skrive nogle hurtige pseudo-kode. 1256 01:05:15,170 --> 01:05:20,380 Per mental model, kan nogen give mig den første linje i pseudo-kode, tak? 1257 01:05:20,380 --> 01:05:23,000 1258 01:05:23,000 --> 01:05:24,270 Hvad ønsker jeg at gøre? 1259 01:05:24,270 --> 01:05:27,070 >> STUDENT: Mens listen er ude af drift. 1260 01:05:27,070 --> 01:05:30,630 >> JASON HIRSCHHORN: OK, mens listen er ude af drift. 1261 01:05:30,630 --> 01:05:33,540 Og hvad mener du med "ude af drift?" 1262 01:05:33,540 --> 01:05:34,960 >> STUDENT: Mens [uhørligt] 1263 01:05:34,960 --> 01:05:36,210 ikke er sorteret. 1264 01:05:36,210 --> 01:05:38,460 1265 01:05:38,460 --> 01:05:40,290 >> JASON HIRSCHHORN: Mens listen er ude af drift, hvad gør vi? 1266 01:05:40,290 --> 01:05:44,200 Giv mig den anden linje, please, Marcus. 1267 01:05:44,200 --> 01:05:47,186 >> STUDENT: Så find den næste mindste tal. 1268 01:05:47,186 --> 01:05:49,000 Dette vil blive indrykket. 1269 01:05:49,000 --> 01:05:55,140 >> JASON HIRSCHHORN: Så find det næstmindste antal. 1270 01:05:55,140 --> 01:05:56,460 Og så en anden? 1271 01:05:56,460 --> 01:06:01,030 Når vi finder den næstmindste nummer, hvad gør vi? 1272 01:06:01,030 --> 01:06:03,010 Jeg har tænkt mig at sige finde det mindste antal. 1273 01:06:03,010 --> 01:06:04,820 Det er, hvad vi ønsker at gøre. 1274 01:06:04,820 --> 01:06:06,210 >> Så find det mindste antal. 1275 01:06:06,210 --> 01:06:08,061 Så hvad gør vi? 1276 01:06:08,061 --> 01:06:09,480 >> STUDENT: [uhørligt] til begyndelsen. 1277 01:06:09,480 --> 01:06:10,680 >> JASON HIRSCHHORN: Undskyld? 1278 01:06:10,680 --> 01:06:12,700 >> STUDENT: Placer den i begyndelsen af ​​listen. 1279 01:06:12,700 --> 01:06:18,540 >> JASON HIRSCHHORN: Så placere den i begyndelsen af ​​listen. 1280 01:06:18,540 --> 01:06:20,140 Og hvad gør vi for at de ting der var i begyndelsen 1281 01:06:20,140 --> 01:06:20,830 af listen, right? 1282 01:06:20,830 --> 01:06:21,910 Vi overskrive noget. 1283 01:06:21,910 --> 01:06:23,130 Så hvor skal vi sætte det? 1284 01:06:23,130 --> 01:06:24,120 Ja, Anna? 1285 01:06:24,120 --> 01:06:25,520 >> STUDENT: Hvor den mindste nummer var? 1286 01:06:25,520 --> 01:06:32,530 >> JASON Hirshhorn: Så læg begyndelsen af den liste, hvor 1287 01:06:32,530 --> 01:06:35,180 mindste tal var. 1288 01:06:35,180 --> 01:06:38,510 Så mens listen er ude af drift, finder det mindste antal, som anbringes i 1289 01:06:38,510 --> 01:06:40,630 begyndelsen af ​​listen, satte begyndelsen af ​​den liste, hvor 1290 01:06:40,630 --> 01:06:42,900 mindste tal var. 1291 01:06:42,900 --> 01:06:45,780 Marcus, kan du omformulere denne linje mens listen er i orden? 1292 01:06:45,780 --> 01:06:51,160 1293 01:06:51,160 --> 01:06:53,900 >> STUDENT: Selvom tallene ikke er sorteret? 1294 01:06:53,900 --> 01:06:55,920 >> JASON Hirshhorn: OK, så for at ved, at tallene ikke har været 1295 01:06:55,920 --> 01:06:58,670 sorteret, hvad skal vi gøre? 1296 01:06:58,670 --> 01:07:00,640 Hvor meget har vi brug for at gå gennem denne liste? 1297 01:07:00,640 --> 01:07:09,650 >> STUDENT: Så jeg gætte en for-løkke, eller mens mens cifrene kontrolleret er mindre 1298 01:07:09,650 --> 01:07:11,900 end længden af ​​listen? 1299 01:07:11,900 --> 01:07:13,160 >> JASON Hirshhorn: OK, det er godt. 1300 01:07:13,160 --> 01:07:15,000 Jeg tror, ​​jeg misphrased mit spørgsmål dårligt. 1301 01:07:15,000 --> 01:07:15,990 Jeg prøvede bare at komme på vi er nødt til at gå 1302 01:07:15,990 --> 01:07:17,580 gennem hele listen. 1303 01:07:17,580 --> 01:07:20,490 Så mens listen er ude af drift, for mig, er svært at kortlægge på. 1304 01:07:20,490 --> 01:07:24,940 Men dybest set, det er hvordan Jeg mener om dette. 1305 01:07:24,940 --> 01:07:28,880 Gå gennem hele listen, skal du finde mindste tal, placer den i 1306 01:07:28,880 --> 01:07:30,130 begyndelse - faktisk, du har ret. 1307 01:07:30,130 --> 01:07:31,380 Lad os sætte dem begge. 1308 01:07:31,380 --> 01:07:33,470 1309 01:07:33,470 --> 01:07:39,050 >> Så mens listen er ude af drift, vi nødt til at gå igennem hele listen 1310 01:07:39,050 --> 01:07:42,250 én gang, finde det mindste tal, sted det i starten af ​​listen, sætte 1311 01:07:42,250 --> 01:07:45,430 begyndelsen af ​​den liste, hvor mindste tal var og derefter, hvis det 1312 01:07:45,430 --> 01:07:47,460 Listen er stadig ude af drift, vi har kom til at gå gennem denne 1313 01:07:47,460 --> 01:07:48,620 processen igen, ikke sandt? 1314 01:07:48,620 --> 01:07:51,610 Det er derfor, udvælgelse sortere, Big-O runtime udvælgelse slags, anyone? 1315 01:07:51,610 --> 01:07:52,830 >> STUDENT: n potens. 1316 01:07:52,830 --> 01:07:53,590 >> JASON Hirshhorn: n potens. 1317 01:07:53,590 --> 01:07:57,040 Fordi ligesom Marcus og jeg har lige indset her, vi nødt til at 1318 01:07:57,040 --> 01:08:00,310 gå gennem listen liste antal gange. 1319 01:08:00,310 --> 01:08:03,420 Så går gennem noget af længde n n antal gange 1320 01:08:03,420 --> 01:08:04,990 er faktisk n potens. 1321 01:08:04,990 --> 01:08:08,100 >> Så dette er vores pseudokode. 1322 01:08:08,100 --> 01:08:09,360 Det ser meget godt ud. 1323 01:08:09,360 --> 01:08:11,870 Er der nogen har nogen spørgsmål om pseudokode? 1324 01:08:11,870 --> 01:08:14,440 Fordi faktisk udvælgelse slags bør sandsynligvis kommer den ene til en, kode fra 1325 01:08:14,440 --> 01:08:14,980 pseudokode. 1326 01:08:14,980 --> 01:08:17,569 Så spørgsmål om logik pseudokode? 1327 01:08:17,569 --> 01:08:18,819 Spørg det nu. 1328 01:08:18,819 --> 01:08:22,609 1329 01:08:22,609 --> 01:08:25,379 >> Valg slags - mens listen er ude af orden, vi kommer til at gå igennem det 1330 01:08:25,379 --> 01:08:27,529 og finde den mindste hver gang og sætte det i front. 1331 01:08:27,529 --> 01:08:33,470 Så mens listen er i orden, kan nogen give mig den linje kode, der 1332 01:08:33,470 --> 01:08:39,689 har ikke givet mig en linje kode endnu, please? 1333 01:08:39,689 --> 01:08:40,939 Det lyder som en hvad? 1334 01:08:40,939 --> 01:08:43,669 1335 01:08:43,669 --> 01:08:44,649 >> STUDENT: Det er en for-løkke. 1336 01:08:44,649 --> 01:08:45,830 >> JASON Hirshhorn: Det lyder gerne en for-løkke. 1337 01:08:45,830 --> 01:08:47,653 OK, kan du give mig for-løkken? 1338 01:08:47,653 --> 01:08:48,925 For - 1339 01:08:48,925 --> 01:08:50,219 >> STUDENT: Jeg lig 0. 1340 01:08:50,219 --> 01:08:52,705 >> JASON Hirshhorn: I eller - 1341 01:08:52,705 --> 01:08:55,111 hvad mangler vi? 1342 01:08:55,111 --> 01:08:56,819 Hvad går lige her? 1343 01:08:56,819 --> 01:08:57,550 >> STUDENT: Int. 1344 01:08:57,550 --> 01:08:59,270 >> JASON Hirshhorn: Præcis. 1345 01:08:59,270 --> 01:09:02,590 (Int i = 0; - 1346 01:09:02,590 --> 01:09:07,843 >> STUDENT: i 01:09:09,319 >> JASON Hirshhorn: Nailed det, Jeff. 1348 01:09:09,319 --> 01:09:10,660 Vi går gennem listen, right? 1349 01:09:10,660 --> 01:09:11,880 Vi har set, at kode før. 1350 01:09:11,880 --> 01:09:12,850 Perfect. 1351 01:09:12,850 --> 01:09:14,790 Så lad os sætte vores krøllede parenteser her. 1352 01:09:14,790 --> 01:09:17,859 Jeg har tænkt mig at sætte nogle krøllede parenteser her. 1353 01:09:17,859 --> 01:09:21,660 >> Så mens det er 0, er vi nødt til at gå gennem hele listen. 1354 01:09:21,660 --> 01:09:26,612 Så hver gang vi gå gennem listen, Hvad ønsker vi at holde styr på? 1355 01:09:26,612 --> 01:09:28,260 >> STUDENT: Hvis nogle swaps foretages. 1356 01:09:28,260 --> 01:09:29,069 >> JASON Hirshhorn: Find det mindste antal. 1357 01:09:29,069 --> 01:09:31,479 Så vi skal nok holde styr på det mindste antal hver gang. 1358 01:09:31,479 --> 01:09:34,590 Så linje kan jeg gøre for at holde styr af det mindste tal? 1359 01:09:34,590 --> 01:09:37,720 Aleha, hvordan kan jeg beholde styr på noget? 1360 01:09:37,720 --> 01:09:38,460 >> STUDENT: Start en ny variabel. 1361 01:09:38,460 --> 01:09:39,390 >> JASON Hirshhorn: Start en ny variabel. 1362 01:09:39,390 --> 01:09:40,069 Så lad os oprette en variabel. 1363 01:09:40,069 --> 01:09:41,830 Hvilken type? 1364 01:09:41,830 --> 01:09:42,930 >> STUDENT: Int. 1365 01:09:42,930 --> 01:09:43,710 >> JASON Hirshhorn: Int. 1366 01:09:43,710 --> 01:09:44,939 Lad os kalde det det mindste. 1367 01:09:44,939 --> 01:09:47,600 Og hvad betyder det lige, når vi er lige begyndt? 1368 01:09:47,600 --> 01:09:48,910 Vi har ikke gået gennem listen endnu. 1369 01:09:48,910 --> 01:09:50,540 Vi er ved første del af liste vores første gang igennem. 1370 01:09:50,540 --> 01:09:51,930 Hvad gør det lige, mindste tal? 1371 01:09:51,930 --> 01:09:54,140 >> STUDENT: værdier, jeg. 1372 01:09:54,140 --> 01:09:54,900 >> JASON Hirshhorn: værdier, jeg. 1373 01:09:54,900 --> 01:09:56,980 Det lyder helt rigtigt, ikke? 1374 01:09:56,980 --> 01:09:59,590 Det mindste antal i begyndelsen er, hvor vi er. 1375 01:09:59,590 --> 01:10:01,960 Så nu har vi vores mindste, og vi har brug for at gå gennem hele listen og 1376 01:10:01,960 --> 01:10:05,080 sammenligne dette mindste til alt andet. 1377 01:10:05,080 --> 01:10:08,150 Så går vi hen gennem listen igen? 1378 01:10:08,150 --> 01:10:08,630 Michael? 1379 01:10:08,630 --> 01:10:10,000 >> STUDENT: Du er nødt til at gøre anden for løkke. 1380 01:10:10,000 --> 01:10:10,383 >> JASON Hirshhorn: Endnu for loop. 1381 01:10:10,383 --> 01:10:11,276 Lad os gøre det. 1382 01:10:11,276 --> 01:10:12,540 Giv mig noget kode. 1383 01:10:12,540 --> 01:10:13,790 >> STUDENT: For loop - 1384 01:10:13,790 --> 01:10:16,750 1385 01:10:16,750 --> 01:10:19,470 for de mindste - 1386 01:10:19,470 --> 01:10:23,040 1387 01:10:23,040 --> 01:10:25,770 bare int j, kan man sige? 1388 01:10:25,770 --> 01:10:31,150 = 0, således at - 1389 01:10:31,150 --> 01:10:34,014 1390 01:10:34,014 --> 01:10:35,710 >> JASON Hirshhorn: Jamen, hvis vi ønsker at gå igennem hele listen - 1391 01:10:35,710 --> 01:10:37,847 >> STUDENT: j 01:10:42,140 1393 01:10:42,140 --> 01:10:42,405 >> JASON Hirshhorn: Fantastic. 1394 01:10:42,405 --> 01:10:46,100 Vi kommer til at gå igennem for-løkken igen. 1395 01:10:46,100 --> 01:10:51,380 Og hvordan finder vi den mindste tal? 1396 01:10:51,380 --> 01:10:52,630 Tom? 1397 01:10:52,630 --> 01:10:54,570 1398 01:10:54,570 --> 01:11:00,520 Vi har den nuværende mindste tal, så hvordan finder vi den nye mindste? 1399 01:11:00,520 --> 01:11:07,200 >> STUDENT: Vi kan kontrollere, om den mindste tal, vi har, er større end 1400 01:11:07,200 --> 01:11:09,040 værdier beslag j. 1401 01:11:09,040 --> 01:11:14,740 >> JASON Hirshhorn: Så hvis mindste er større end værdier beslag j. 1402 01:11:14,740 --> 01:11:19,350 Så hvis vores nuværende mindste er større end - 1403 01:11:19,350 --> 01:11:21,770 Jeg har tænkt mig at flytte disse to linjer kode derude for et sekund. 1404 01:11:21,770 --> 01:11:26,010 Fordi før vi gør noget swapping, vi nødt til at gå igennem hele listen. 1405 01:11:26,010 --> 01:11:28,880 Så dette pseudokode burde faktisk være uden for den indre for-løkke. 1406 01:11:28,880 --> 01:11:30,390 Så gå igennem hele listen. 1407 01:11:30,390 --> 01:11:34,520 Hvis mindste er større end værdier j hvad så? 1408 01:11:34,520 --> 01:11:37,830 >> STUDENT: Så mindste lig værdierne j. 1409 01:11:37,830 --> 01:11:41,190 1410 01:11:41,190 --> 01:11:42,600 >> JASON Hirshhorn: Fantastic. 1411 01:11:42,600 --> 01:11:44,580 Et hurtigt spørgsmål - 1412 01:11:44,580 --> 01:11:47,236 første gang vi går gennem denne løkke, Jeg kommer til at være lig med 0, er j går 1413 01:11:47,236 --> 01:11:50,710 til lig med 0, når vi kommer her. 1414 01:11:50,710 --> 01:11:52,410 Så vi kommer til at sammenligne et nummer til sig selv. 1415 01:11:52,410 --> 01:11:53,660 Er det effektivt? 1416 01:11:53,660 --> 01:11:57,260 1417 01:11:57,260 --> 01:11:58,390 Nej, det er ikke rigtig effektiv. 1418 01:11:58,390 --> 01:12:02,915 Så gør vores j nødt til at gå fra 0 til n hver gang? 1419 01:12:02,915 --> 01:12:06,310 Har vi altid nødt til at tjekke gennem hele listen? 1420 01:12:06,310 --> 01:12:06,520 [Uhørligt]? 1421 01:12:06,520 --> 01:12:07,564 >> STUDENT: Start med i stedet for. 1422 01:12:07,564 --> 01:12:09,405 >> JASON Hirshhorn: j dåse starte med hvad? 1423 01:12:09,405 --> 01:12:09,990 >> STUDENT: i. 1424 01:12:09,990 --> 01:12:13,040 >> JASON Hirshhorn: j kan starte med jeg. 1425 01:12:13,040 --> 01:12:18,840 Så nu er vi sammenligne starter med den, vi er på. 1426 01:12:18,840 --> 01:12:21,020 Men selv da, er det som effektiv som muligt? 1427 01:12:21,020 --> 01:12:22,320 >> STUDENT: i + 1. 1428 01:12:22,320 --> 01:12:25,420 >> JASON Hirshhorn: i + 1 synes at være de mest effektive, fordi vi 1429 01:12:25,420 --> 01:12:26,120 allerede har jeg. 1430 01:12:26,120 --> 01:12:28,100 Vi angiver, at da mindste i linie 15. 1431 01:12:28,100 --> 01:12:29,350 Vi kommer til at starte med næste automatisk. 1432 01:12:29,350 --> 01:12:34,470 1433 01:12:34,470 --> 01:12:38,540 Så vi går igennem for-løkken. 1434 01:12:38,540 --> 01:12:39,620 Vi vil gå igennem hver gang. 1435 01:12:39,620 --> 01:12:40,860 Vi vil gå igennem et antal gange. 1436 01:12:40,860 --> 01:12:42,860 Nu har vi fået gennem denne indre for-løkke. 1437 01:12:42,860 --> 01:12:44,350 Vi har den mindste værdi sparer. 1438 01:12:44,350 --> 01:12:46,045 Vi har brug for at placere det på det begyndelsen af ​​listen. 1439 01:12:46,045 --> 01:12:48,390 Så hvordan skal jeg placere det i begyndelsen af ​​listen? 1440 01:12:48,390 --> 01:12:51,290 1441 01:12:51,290 --> 01:12:55,926 Hvad er den variabel, der refererer til begyndelsen af ​​listen? 1442 01:12:55,926 --> 01:13:00,500 Vi er i denne uden for loop, så hvad refererer til 1443 01:13:00,500 --> 01:13:01,280 begyndelsen af ​​listen? 1444 01:13:01,280 --> 01:13:02,880 >> STUDENT: værdier, jeg. 1445 01:13:02,880 --> 01:13:03,510 >> JASON Hirshhorn: Præcis højre. 1446 01:13:03,510 --> 01:13:04,650 Værdier i er begyndelsen af ​​- 1447 01:13:04,650 --> 01:13:06,320 eller ked af det, ikke begyndelsen. 1448 01:13:06,320 --> 01:13:07,090 Det var forvirrende. 1449 01:13:07,090 --> 01:13:11,620 Det er, hvor vi er i starten af usorteret del af listen. 1450 01:13:11,620 --> 01:13:12,800 Så værdier, jeg. 1451 01:13:12,800 --> 01:13:14,050 Og hvad betyder det lige? 1452 01:13:14,050 --> 01:13:15,925 1453 01:13:15,925 --> 01:13:17,326 >> STUDENT: Mindst. 1454 01:13:17,326 --> 01:13:18,862 >> JASON Hirshhorn: Værdier i lig hvad? 1455 01:13:18,862 --> 01:13:19,310 >> STUDENT: Mindst. 1456 01:13:19,310 --> 01:13:20,030 >> JASON Hirshhorn: Mindst. 1457 01:13:20,030 --> 01:13:20,980 Præcis højre. 1458 01:13:20,980 --> 01:13:23,510 Så vi placerer det i begyndelsen af listen, og nu er vi nødt til at sætte 1459 01:13:23,510 --> 01:13:25,710 begyndelsen af ​​den liste, hvor det mindste antal var. 1460 01:13:25,710 --> 01:13:29,700 Så hvordan skriver jeg, hvor mindste tal var? 1461 01:13:29,700 --> 01:13:31,670 Værdier for hvad? 1462 01:13:31,670 --> 01:13:33,170 >> STUDENT: 0. 1463 01:13:33,170 --> 01:13:34,090 >> JASON Hirshhorn: Den lille nummer er på 0? 1464 01:13:34,090 --> 01:13:35,340 >> STUDENT: Ja. 1465 01:13:35,340 --> 01:13:38,680 1466 01:13:38,680 --> 01:13:39,910 >> JASON Hirshhorn: Hvad hvis de mindste antal var ved udgangen af 1467 01:13:39,910 --> 01:13:40,860 denne usorteret liste? 1468 01:13:40,860 --> 01:13:42,460 >> STUDENT: Undskyld, hvad var spørgsmålet? 1469 01:13:42,460 --> 01:13:44,020 >> JASON Hirshhorn: Hvor er det mindste tal? 1470 01:13:44,020 --> 01:13:46,940 Vi tog den mindste og sætte det på begynder med denne linje lige her. 1471 01:13:46,940 --> 01:13:48,987 >> STUDENT: Det burde have været opbevaret i nogle - 1472 01:13:48,987 --> 01:13:50,510 >> STUDENT: Værdier j. 1473 01:13:50,510 --> 01:13:51,520 >> JASON Hirshhorn: Jamen, det er ikke nødvendigvis værdier j. 1474 01:13:51,520 --> 01:13:54,100 Det behøver ikke engang eksisterer på dette punkt. 1475 01:13:54,100 --> 01:13:55,960 >> STUDENT: Du er nødt til at erklære en variabel tidligere og 1476 01:13:55,960 --> 01:13:58,230 derefter tildele den til - 1477 01:13:58,230 --> 01:14:01,150 når du finder det mindste tal, tildele indekset for dette tal til 1478 01:14:01,150 --> 01:14:02,480 nogle variabel eller noget lignende. 1479 01:14:02,480 --> 01:14:04,790 >> JASON Hirshhorn: Så kan du sige det igen? 1480 01:14:04,790 --> 01:14:08,390 >> STUDENT: Så hvor du erklærede int mindste, bør du også erklære int 1481 01:14:08,390 --> 01:14:10,750 mindste indeks = i, eller noget lignende. 1482 01:14:10,750 --> 01:14:13,280 >> JASON Hirshhorn: Så hvor jeg int mindste, skal jeg ikke kun holde styr 1483 01:14:13,280 --> 01:14:16,150 af værdien, men placeringen. 1484 01:14:16,150 --> 01:14:20,850 int smallest_location = i dette tilfælde, vil vi bare gør jeg. 1485 01:14:20,850 --> 01:14:22,390 Vi har brug for at vide, hvor det er. 1486 01:14:22,390 --> 01:14:26,820 Vi fik til slutningen af ​​koden, og vi indså vi havde ingen idé om, hvor det var. 1487 01:14:26,820 --> 01:14:29,810 Og så igen, vi er kortlægning dette på én til én. 1488 01:14:29,810 --> 01:14:32,890 Du fyre kodning dette på din egen vilje sandsynligvis komme til det samme problem. 1489 01:14:32,890 --> 01:14:34,130 Hvordan dælen finder jeg det? 1490 01:14:34,130 --> 01:14:36,720 Og så skal du indse, vent, jeg nødt til at holde styr på det. 1491 01:14:36,720 --> 01:14:38,500 >> Så hvis mindste er større end værdierne j. 1492 01:14:38,500 --> 01:14:39,740 Vi satte mindste svarer til værdier j. 1493 01:14:39,740 --> 01:14:42,090 Hvad har vi brug for at ændre? 1494 01:14:42,090 --> 01:14:43,710 Constantin, hvad ellers gøre vi nødt til at ændre? 1495 01:14:43,710 --> 01:14:44,560 >> STUDENT: Den placering. 1496 01:14:44,560 --> 01:14:45,270 >> JASON Hirshhorn: Præcis. 1497 01:14:45,270 --> 01:14:46,925 Så giv mig denne linje i koden. 1498 01:14:46,925 --> 01:14:53,310 >> STUDENT: smallest_location = j. 1499 01:14:53,310 --> 01:14:54,790 >> JASON Hirshhorn: Præcis. 1500 01:14:54,790 --> 01:14:58,210 Og derefter ned i slutningen, hvis vi ønsker at sætte starten af ​​listen, hvor 1501 01:14:58,210 --> 01:15:00,790 det mindste antal var, hvor vi henviser til, hvor 1502 01:15:00,790 --> 01:15:02,200 mindste tal var? 1503 01:15:02,200 --> 01:15:03,580 Marcus? 1504 01:15:03,580 --> 01:15:08,530 >> STUDENT: Den mindste tal var placeret på mindste placering. 1505 01:15:08,530 --> 01:15:12,230 >> JASON Hirshhorn: Så på værdier smallest_location. 1506 01:15:12,230 --> 01:15:14,700 Og hvad skal vi sætte der? 1507 01:15:14,700 --> 01:15:17,600 Begyndelsen af liste, hvad er det? 1508 01:15:17,600 --> 01:15:19,710 >> STUDENT: Jamen, vi ikke rigtig ved, længere, fordi vi har overskrevet. 1509 01:15:19,710 --> 01:15:23,250 Så det er en byttet placeringer af disse to linjer? 1510 01:15:23,250 --> 01:15:26,110 Hvis du skifter de to linjer rundt. 1511 01:15:26,110 --> 01:15:30,740 >> JASON Hirshhorn: OK, så vi ikke længere, fordi vi har nulstillet den linje 1512 01:15:30,740 --> 01:15:31,960 før værdier I til mindste. 1513 01:15:31,960 --> 01:15:33,810 Så vi mistet denne oprindelige værdi. 1514 01:15:33,810 --> 01:15:37,350 Så du siger swap disse to linjer. 1515 01:15:37,350 --> 01:15:41,780 Så nu sætte starten af ​​listen hvor det mindste antal var. 1516 01:15:41,780 --> 01:15:47,060 Så smallest_location lig værdier, jeg. 1517 01:15:47,060 --> 01:15:51,310 Det bevæger sig i begyndelsen af ​​dette usorteret del af listen til 1518 01:15:51,310 --> 01:15:52,090 mindste placering. 1519 01:15:52,090 --> 01:15:54,860 Og derefter i værdier, jeg vi flytter at mindste tal. 1520 01:15:54,860 --> 01:15:57,450 >> Giver det mening, hvorfor vi havde at gøre at bytte? 1521 01:15:57,450 --> 01:15:59,650 Vi ville have overskrevet denne værdi - en anden ting du sandsynligvis ville have 1522 01:15:59,650 --> 01:16:02,740 regnet ud og fandt i BNP. 1523 01:16:02,740 --> 01:16:05,310 Så vi har taget sig af alle pseudokode. 1524 01:16:05,310 --> 01:16:10,935 Er der noget andet, vi nødt til at skrive her? 1525 01:16:10,935 --> 01:16:14,911 Kan nogen tænke på noget? 1526 01:16:14,911 --> 01:16:16,180 >> STUDENT: Hvordan kan du vide når du er færdig? 1527 01:16:16,180 --> 01:16:17,680 >> JASON Hirshhorn: Hvordan kan vi vide, hvornår vi er færdige? 1528 01:16:17,680 --> 01:16:18,890 Godt spørgsmål. 1529 01:16:18,890 --> 01:16:21,684 Så hvordan kan vi vide, når vi er færdige. 1530 01:16:21,684 --> 01:16:24,720 >> STUDENT: Opret en variabel til at holde tal af hvis der er en swap lavet eller ikke 1531 01:16:24,720 --> 01:16:27,810 og gå gennem et pass. 1532 01:16:27,810 --> 01:16:30,180 >> JASON Hirshhorn: OK. 1533 01:16:30,180 --> 01:16:31,800 Det ville fungere i boble slags. 1534 01:16:31,800 --> 01:16:35,210 Men for udvælgelse slags, hvis vi ikke gør lave en swap, kan det bare være 1535 01:16:35,210 --> 01:16:38,670 fordi den mindste værdi er i det sin rette placering. 1536 01:16:38,670 --> 01:16:41,240 Vi kunne have en liste 1, 2, 4, 3. 1537 01:16:41,240 --> 01:16:42,830 Anden gang gennem vi vil ikke gøre nogen swaps. 1538 01:16:42,830 --> 01:16:47,260 Vi vil være på nummer 2, men vi vil stadig nødt til at holde ud. 1539 01:16:47,260 --> 01:16:49,390 Så har vi brug for at holde styr på, når vi er færdig, eller skal vi bare ønsker at gå 1540 01:16:49,390 --> 01:16:50,640 indtil dette er færdig? 1541 01:16:50,640 --> 01:16:54,098 1542 01:16:54,098 --> 01:16:56,740 >> STUDENT: Vi kan bare gå indtil den er færdig. 1543 01:16:56,740 --> 01:16:58,090 >> JASON Hirshhorn: Vi kan bare gå, indtil dette er afsluttet. 1544 01:16:58,090 --> 01:17:01,720 I boble sortere, er du helt rigtigt, Jeff og Aleha, med din løsning - 1545 01:17:01,720 --> 01:17:04,990 det er dejligt at holde styr på, hvor mange swaps du har lavet, fordi der i boble 1546 01:17:04,990 --> 01:17:07,920 sortere, hvis du gør i virkeligheden gør ingen swaps, du er færdig, og du kan måske klippe din 1547 01:17:07,920 --> 01:17:09,000 problem lidt ned. 1548 01:17:09,000 --> 01:17:11,440 Men for udvælgelse slags, har du virkelig kom til at gå igennem til slutningen af 1549 01:17:11,440 --> 01:17:14,940 liste hver gang. 1550 01:17:14,940 --> 01:17:16,200 >> Så det er det. 1551 01:17:16,200 --> 01:17:18,530 Vi har to minutter tilbage. 1552 01:17:18,530 --> 01:17:21,560 Lad os gøre alle. 1553 01:17:21,560 --> 01:17:24,340 Lad mig bare åbne Find her og gøre sikker på at jeg faktisk ringer op - 1554 01:17:24,340 --> 01:17:25,610 Jeg ringer ikke til boble slags. 1555 01:17:25,610 --> 01:17:29,230 Lad os ændre dette til udvælgelse slags. 1556 01:17:29,230 --> 01:17:31,060 gøre alt. / finde. 1557 01:17:31,060 --> 01:17:32,360 Lad os finde 42. 1558 01:17:32,360 --> 01:17:38,110 Denne gang vi kommer til at bestå en usorteret liste, fordi det skulle sortere 1559 01:17:38,110 --> 01:17:43,790 første, pr find koden - skal sortere først ved hjælp af vores slags funktion og derefter 1560 01:17:43,790 --> 01:17:44,995 kigge efter noget. 1561 01:17:44,995 --> 01:17:46,245 Fingrene krydsede alle. 1562 01:17:46,245 --> 01:17:48,530 1563 01:17:48,530 --> 01:17:49,370 >> Åh min godhed. 1564 01:17:49,370 --> 01:17:50,800 Whoa, mit hjerte bankede. 1565 01:17:50,800 --> 01:17:52,320 Så det er korrekt. 1566 01:17:52,320 --> 01:17:57,270 Faktisk, hvis vi løb dette mere udførligt, koden, så vidt jeg kan 1567 01:17:57,270 --> 01:17:59,280 fortælle, er helt korrekt. 1568 01:17:59,280 --> 01:18:02,150 Der er nogle forslag Jeg ville have for dig. 1569 01:18:02,150 --> 01:18:06,215 For eksempel, 15 og 16 synes lidt overflødigt. 1570 01:18:06,215 --> 01:18:09,450 Det virker som om du ikke nødvendigvis nødt til at spare både dem. 1571 01:18:09,450 --> 01:18:12,790 Hvis du har den mindste placering, du kan nemt finde den mindste værdi af 1572 01:18:12,790 --> 01:18:14,750 bare at skrive værdier af I. 1573 01:18:14,750 --> 01:18:18,100 >> Så hvis jeg skulle klassificering din kode, som jeg vil faktisk være, jeg ville 1574 01:18:18,100 --> 01:18:21,160 sandsynligvis tage et punkt, hvis du omfattede både af disse, fordi du 1575 01:18:21,160 --> 01:18:22,670 behøver ikke begge disse. 1576 01:18:22,670 --> 01:18:25,400 Hvis du har den placering, kan du meget let få værdien. 1577 01:18:25,400 --> 01:18:27,520 Og det virker lidt underligt at gemme dem begge. 1578 01:18:27,520 --> 01:18:31,070 Måske ikke engang tage et punkt, men sikkert kommentere, at der er måske 1579 01:18:31,070 --> 01:18:32,670 ikke et stilistisk valg du behøver at gøre. 1580 01:18:32,670 --> 01:18:35,290 Selvfølgelig koden stadig kører udmærket. 1581 01:18:35,290 --> 01:18:36,860 >> Så desværre ikke gjorde vi komme til boble slags. 1582 01:18:36,860 --> 01:18:37,940 Jeg er ked af det. 1583 01:18:37,940 --> 01:18:39,135 Vi gjorde slut udvælgelse slags. 1584 01:18:39,135 --> 01:18:41,450 Er der nogen, der har nogen endelige spørgsmål om udvælgelse slags? 1585 01:18:41,450 --> 01:18:44,320 1586 01:18:44,320 --> 01:18:47,690 >> OK, før vi hovedet ud, jeg vil have dig at åbne din Chrome-browser. 1587 01:18:47,690 --> 01:18:54,340 Undskyld, det var bare en åbenlys stik for en type af internet browser. 1588 01:18:54,340 --> 01:18:57,770 Du kan åbne op enhver type browser, men det vil sandsynligvis være Chrome. 1589 01:18:57,770 --> 01:19:01,250 Og gå til denne følgende websted - 1590 01:19:01,250 --> 01:19:06,410 sayat.me/cs50. 1591 01:19:06,410 --> 01:19:07,685 Hvis du ikke skriver i din computer lige nu, er du tydeligt 1592 01:19:07,685 --> 01:19:10,210 ikke gør det, Tom. 1593 01:19:10,210 --> 01:19:12,870 >> Og du gøre det enten højre nu eller i den næste time - 1594 01:19:12,870 --> 01:19:14,260 give mig nogle tilbagemeldinger. 1595 01:19:14,260 --> 01:19:15,660 Dette er kun punkt to. 1596 01:19:15,660 --> 01:19:18,060 Vi har mange flere sammen, så jeg har en masse plads til at forbedre. 1597 01:19:18,060 --> 01:19:19,620 Jeg forhåbentlig også gjorde nogle ting godt. 1598 01:19:19,620 --> 01:19:22,160 Så du kan gøre mig alle dårlige, men hvis du også ønsker at give mig en smiley 1599 01:19:22,160 --> 01:19:24,250 ansigt, ville jeg sætte pris på, at så godt. 1600 01:19:24,250 --> 01:19:25,330 Fyld det i. 1601 01:19:25,330 --> 01:19:28,210 >> Og med et minut tilbage, der var uge tre. 1602 01:19:28,210 --> 01:19:30,750 Jeg vil stå uden for en smule hvis du har spørgsmål. 1603 01:19:30,750 --> 01:19:32,220 Jeg vil se jer i foredrag i morgen. 1604 01:19:32,220 --> 01:19:34,742