1 00:00:00,000 --> 00:00:08,532 >> [Glazba svira] 2 00:00:08,532 --> 00:00:12,060 >> ZAMYLA Chan: Prva stvar koju ćete Obavijest o otkriću je da smo već 3 00:00:12,060 --> 00:00:13,450 su kod napisan za nas. 4 00:00:13,450 --> 00:00:15,160 To se zove distribucija code. 5 00:00:15,160 --> 00:00:18,000 Dakle, mi ne samo pisanje vlastitih koda od nule više. 6 00:00:18,000 --> 00:00:22,800 Umjesto toga, mi smo popunjavanja praznine na neki već postojeći kod. 7 00:00:22,800 --> 00:00:27,790 >> Find.c Program traži brojeva popuniti plast sijena, traži 8 00:00:27,790 --> 00:00:32,189 plastu sijena za korisnika podnosi iglom, i to čini pozivom vrsta i 9 00:00:32,189 --> 00:00:35,590 pretraživanja, funkcije definirane u helpers.c. 10 00:00:35,590 --> 00:00:37,670 Dakle find.c je napisano već. 11 00:00:37,670 --> 00:00:40,770 Vaš je zadatak napisati pomagače. 12 00:00:40,770 --> 00:00:41,870 >> Pa što da radimo? 13 00:00:41,870 --> 00:00:44,210 Mi provedbi dvije funkcije. 14 00:00:44,210 --> 00:00:49,030 Pretraga, koji vraća true ako je vrijednost nalazi u plastu sijena, povratka 15 00:00:49,030 --> 00:00:51,370 false ako je vrijednost Ne u plastu sijena. 16 00:00:51,370 --> 00:00:57,990 I onda mi smo također provedbi vrsta koji sortira niz zove vrijednosti. 17 00:00:57,990 --> 00:00:59,960 >> Tako ćemo se borila za pretraživanje. 18 00:00:59,960 --> 00:01:04,560 Traži trenutno se provodi kao slijedne pretrage, ali vi možete učiniti mnogo 19 00:01:04,560 --> 00:01:05,550 bolje od toga. 20 00:01:05,550 --> 00:01:09,910 Linearni traži se provodi u O n vremena, što je prilično sporo. 21 00:01:09,910 --> 00:01:13,850 Iako, to može pretraživati Popis bilo dano na njega. 22 00:01:13,850 --> 00:01:20,130 Vaš posao je da se provede binarni pretragu, koja je pokrenuti vrijeme O iz dnevnika n. 23 00:01:20,130 --> 00:01:21,130 To je prilično brzo. 24 00:01:21,130 --> 00:01:23,170 >> Ali postoji uvjet. 25 00:01:23,170 --> 00:01:27,600 Binary traži se samo traži kroz prethodno sortirani listama. 26 00:01:27,600 --> 00:01:30,370 Zašto je to tako? 27 00:01:30,370 --> 00:01:32,620 >> Pa pogledajmo primjer. 28 00:01:32,620 --> 00:01:36,280 S obzirom na niz vrijednosti, plast, ćemo biti u potrazi 29 00:01:36,280 --> 00:01:37,130 za iglu. 30 00:01:37,130 --> 00:01:40,460 I u ovom primjeru, cijeli broj tri. 31 00:01:40,460 --> 00:01:44,130 Način na koji binarno pretraživanje radi je da Usporedimo srednju vrijednost 32 00:01:44,130 --> 00:01:48,370 polje za igle, poput kako otvorili smo imenika na sredini 33 00:01:48,370 --> 00:01:50,660 stranica u tjednu nula. 34 00:01:50,660 --> 00:01:54,650 >> Dakle, nakon što se usporede srednje vrijednosti igla, možete odbaciti bilo 35 00:01:54,650 --> 00:01:58,530 lijeva ili desna polovica niz zatezanjem svoje granice. 36 00:01:58,530 --> 00:02:03,390 U tom slučaju, od tri, naša iglu je manje od 10, srednja vrijednost, 37 00:02:03,390 --> 00:02:05,990 Pravo granicu može se smanjiti. 38 00:02:05,990 --> 00:02:08,400 No, pokušati napraviti svoje granice kao čvrsto što je više moguće. 39 00:02:08,400 --> 00:02:11,630 Ako srednja vrijednost nije igla, onda znate da ne trebate 40 00:02:11,630 --> 00:02:13,010 uključiti ga u pretraživanje. 41 00:02:13,010 --> 00:02:17,310 Dakle, u pravu si granicu može zategnuti search granice samo jedan maleni malo više, 42 00:02:17,310 --> 00:02:21,770 i tako dalje i tako dalje sve dok nađete svoj iglu. 43 00:02:21,770 --> 00:02:23,480 >> Dakle, ono što ne pseudocode izgledati? 44 00:02:23,480 --> 00:02:28,420 Pa, dok smo još uvijek gleda kroz Popis i još uvijek imaju elemente 45 00:02:28,420 --> 00:02:33,690 gledati u, uzmemo sredinu ljestvice, i usporediti tu srednju vrijednost 46 00:02:33,690 --> 00:02:34,950 naša igla. 47 00:02:34,950 --> 00:02:37,310 Ako su oni jednaki, onda to znači da smo pronašao iglu i što možemo 48 00:02:37,310 --> 00:02:38,990 povratak istina. 49 00:02:38,990 --> 00:02:42,870 >> Inače, ako je igla ispod srednja vrijednost, onda da mi znači 50 00:02:42,870 --> 00:02:47,280 može odbaciti desnu polovicu, a samo traži lijevu stranu polja. 51 00:02:47,280 --> 00:02:51,090 Inače, mi ćemo tražiti desnoj strani polja. 52 00:02:51,090 --> 00:02:54,410 I na kraju, ako ne imati bilo više elemenata ostavili da traži, ali ste 53 00:02:54,410 --> 00:02:58,050 nisu pronašli svoj iglu još, onda vam povratak false jer igla 54 00:02:58,050 --> 00:03:01,890 definitivno nije u plastu sijena. 55 00:03:01,890 --> 00:03:05,270 >> Sada uredan stvar o ovom pseudocode binarno pretraživanje je da to može biti 56 00:03:05,270 --> 00:03:09,940 tumačiti kao bilo iterativni ili rekurzivna provedba. 57 00:03:09,940 --> 00:03:13,810 Tako da će to biti rekurzivna ako zove pretraživač u potrazi 58 00:03:13,810 --> 00:03:17,350 djelovati na bilo polovici polja. 59 00:03:17,350 --> 00:03:21,030 Mi ćemo pokriti rekurziju malo kasnije u Naravno, ali znam da je to 60 00:03:21,030 --> 00:03:24,190 izbor ako želite probati. 61 00:03:24,190 --> 00:03:26,030 >> Sada pogledajmo koje vrste. 62 00:03:26,030 --> 00:03:30,750 Sortiranje traje niz i cijeli broj n, što je veličina polja. 63 00:03:30,750 --> 00:03:34,030 Sada postoje različiti tipovi sorti, a možete pogledati neke 64 00:03:34,030 --> 00:03:36,370 hlačice za demonstracije i objašnjenja. 65 00:03:36,370 --> 00:03:39,580 Tip za povratak naših vrsta funkcija je nevažeće. 66 00:03:39,580 --> 00:03:43,580 Dakle, to znači da nećemo da se vrate bilo niz od vrste. 67 00:03:43,580 --> 00:03:48,140 Mi se zapravo neće promijeniti vrlo Niz koji je donesen u nama. 68 00:03:48,140 --> 00:03:52,290 >> I to je moguće jer su nizovi donijela reference u C. Sad ćemo 69 00:03:52,290 --> 00:03:55,290 više o tome kasnije, ali Bitna razlika između prolazu 70 00:03:55,290 --> 00:03:59,340 u nešto poput cijeli broj i smrti u nizu, je da kada se 71 00:03:59,340 --> 00:04:03,490 prođe u cijeli broj, C samo ide na napraviti kopiju tog cijelog broja i proći 72 00:04:03,490 --> 00:04:04,450 da funkcije. 73 00:04:04,450 --> 00:04:08,530 Izvorna varijabla neće se mijenjati Jednom funkcija završila. 74 00:04:08,530 --> 00:04:12,480 S nizom, s druge strane, to Ne ide to napraviti kopiju, a vi ćete 75 00:04:12,480 --> 00:04:17,910 zapravo se uređivanje Sam vrlo polje. 76 00:04:17,910 --> 00:04:21,269 >> Dakle, jedna vrsta vrste je svojevrsna selekcija. 77 00:04:21,269 --> 00:04:24,750 Izbor vrsta djela s početkom u početak, a onda ponoviti 78 00:04:24,750 --> 00:04:26,820 tijekom i pronaći najmanji element. 79 00:04:26,820 --> 00:04:30,710 I onda zamijeniti ona najmanja Element s prvom. 80 00:04:30,710 --> 00:04:34,360 I onda se preselite na drugi element , Naći pored najmanji 81 00:04:34,360 --> 00:04:38,320 elementa, a zatim da se zamijeniti s Drugi element u polju, jer 82 00:04:38,320 --> 00:04:41,100 Prvi element je već riješeno. 83 00:04:41,100 --> 00:04:45,370 I tako onda ste i dalje za svaki element u identificiranju najmanji 84 00:04:45,370 --> 00:04:47,690 vrijednost i to zamjenom. 85 00:04:47,690 --> 00:04:53,460 >> Jer sam jednako 0, prvi elementa do n minus 1, ideš uspoređivati 86 00:04:53,460 --> 00:04:57,820 svaka sljedeća vrijednost nakon toga i pronaći Indeks minimalne vrijednosti. 87 00:04:57,820 --> 00:05:02,520 Jednom kada pronađete indeks minimalna vrijednost, možete zamijeniti tu vrijednost niza 88 00:05:02,520 --> 00:05:05,930 Minimalna i niz I. 89 00:05:05,930 --> 00:05:09,760 >> Druga vrsta vrste koje možete implementirati je mjehurić vrsta. 90 00:05:09,760 --> 00:05:14,380 Dakle mjehurić sortirati iterates preko popisa Usporedbom susjedne elemente i 91 00:05:14,380 --> 00:05:17,720 zamjene elemenata koji su u pogrešnom redoslijedu. 92 00:05:17,720 --> 00:05:22,380 I na ovaj način, po veličini je element će mjehurić na kraju. 93 00:05:22,380 --> 00:05:28,070 A popis sortira odjednom više nema elementi su zamijenili. 94 00:05:28,070 --> 00:05:31,920 >> Dakle, to su dva primjera vrste algoritmi koji možete provesti za 95 00:05:31,920 --> 00:05:33,230 Program otkriće. 96 00:05:33,230 --> 00:05:37,350 Nakon što ste završili vrsta, a vi ste obaviti pretragu, gotov si. 97 00:05:37,350 --> 00:05:39,720 Moje ime je Zamyla, a to je CS50. 98 00:05:39,720 --> 00:05:46,987 >> [Glazba svira]