1
00:00:00,000 --> 00:00:08,532
>> [Redare a muzicii]

2
00:00:08,532 --> 00:00:12,060
>> ZAMYLA CHAN: Primul lucru pe care s-ar putea
aviz cu privire la descoperire este că noi deja

3
00:00:12,060 --> 00:00:13,450
au cod scris pentru noi.

4
00:00:13,450 --> 00:00:15,160
Aceasta se numește cod de distribuție.

5
00:00:15,160 --> 00:00:18,000
Deci, nu doar scris propria noastră
mai cod de la zero.

6
00:00:18,000 --> 00:00:22,800
Mai degrabă, suntem completarea golurilor
în unele cod pre-existent.

7
00:00:22,800 --> 00:00:27,790
>> Programul find.c solicită numere
pentru a umple carul cu fân, caută

8
00:00:27,790 --> 00:00:32,189
claie de fân pentru un ac de utilizator prezentate,
și-l face acest lucru prin apel tip și

9
00:00:32,189 --> 00:00:35,590
de căutare, funcții definite
în helpers.c.

10
00:00:35,590 --> 00:00:37,670
Astfel find.c este scris deja.

11
00:00:37,670 --> 00:00:40,770
Treaba ta este de a scrie ajutoare.

12
00:00:40,770 --> 00:00:41,870
>> Deci, ce facem?

13
00:00:41,870 --> 00:00:44,210
Suntem punerea în aplicare a două funcții.

14
00:00:44,210 --> 00:00:49,030
De căutare, care returneaza true daca o valoare
se găsește în carul cu fân, revenind

15
00:00:49,030 --> 00:00:51,370
false dacă valoarea este
nu în carul cu fân.

16
00:00:51,370 --> 00:00:57,990
Și apoi vom punere în aplicare, de asemenea, un fel
care sortează matrice numita valori.

17
00:00:57,990 --> 00:00:59,960
>> Deci, haideți să abordeze căutare.

18
00:00:59,960 --> 00:01:04,560
Căutare este în prezent pusă în aplicare ca o
căutare liniară, dar puteți face mult

19
00:01:04,560 --> 00:01:05,550
mai mult decât atât.

20
00:01:05,550 --> 00:01:09,910
Căutare liniară este implementat în O
de n timp, care este destul de lentă.

21
00:01:09,910 --> 00:01:13,850
Deși, se poate căuta
orice listă dat să-l.

22
00:01:13,850 --> 00:01:20,130
Treaba ta este de a implementa căutare binară,
care a rulat timp O, de n log.

23
00:01:20,130 --> 00:01:21,130
Asta e destul de repede.

24
00:01:21,130 --> 00:01:23,170
>> Dar există o prevedere.

25
00:01:23,170 --> 00:01:27,600
Binar de căutare poate căuta numai
prin liste de pre-sortate.

26
00:01:27,600 --> 00:01:30,370
De ce este asta?

27
00:01:30,370 --> 00:01:32,620
>> Ei bine, să ne uităm la un exemplu.

28
00:01:32,620 --> 00:01:36,280
Având în vedere o serie de valori, carul cu fân,
vom fi uitat

29
00:01:36,280 --> 00:01:37,130
pentru un ac.

30
00:01:37,130 --> 00:01:40,460
Și în acest exemplu,
întreg trei.

31
00:01:40,460 --> 00:01:44,130
Modul în care funcționează binar de căutare este că
vom compara valoarea de mijloc a

32
00:01:44,130 --> 00:01:48,370
matrice pentru a acului, mai mult ca și cum
am deschis o agendă telefonică la mijloc

33
00:01:48,370 --> 00:01:50,660
pagina in saptamana zero.

34
00:01:50,660 --> 00:01:54,650
>> Deci, după compararea valorii de mijloc a
acul, puteți să aruncați fie

35
00:01:54,650 --> 00:01:58,530
stânga sau jumătatea din dreapta a matrice
prin strângerea limitele impuse.

36
00:01:58,530 --> 00:02:03,390
În acest caz, deoarece trei, ac nostru,
este mai mic de 10, valoarea de mijloc,

37
00:02:03,390 --> 00:02:05,990
drept legat poate scădea.

38
00:02:05,990 --> 00:02:08,400
Dar încercați să faceți limite de
la fel de bine ca posibil.

39
00:02:08,400 --> 00:02:11,630
Dacă valoarea de mijloc nu este acul,
atunci știți că nu aveți nevoie să

40
00:02:11,630 --> 00:02:13,010
include în căutarea.

41
00:02:13,010 --> 00:02:17,310
Deci, ai dreptate legat pot strânge
limite de căutare doar un pic mai mult,

42
00:02:17,310 --> 00:02:21,770
și așa mai departe și așa mai departe până când
veți găsi ac ta.

43
00:02:21,770 --> 00:02:23,480
>> Deci, ce pseudocod arata ca?

44
00:02:23,480 --> 00:02:28,420
Ei bine, în timp ce suntem încă în căutarea prin
lista și încă mai au elemente la

45
00:02:28,420 --> 00:02:33,690
uita-te la, vom lua la mijlocul listei,
și compara ca valoare medie a

46
00:02:33,690 --> 00:02:34,950
ac nostru.

47
00:02:34,950 --> 00:02:37,310
Dacă sunt egali, atunci înseamnă că ne-am
găsit acul și putem

48
00:02:37,310 --> 00:02:38,990
return true.

49
00:02:38,990 --> 00:02:42,870
>> Altfel, dacă acul este mai mică
valoarea de mijloc, atunci înseamnă că ne-am

50
00:02:42,870 --> 00:02:47,280
se poate renunța la jumătatea din dreapta, și doar
căutați în partea stângă a tabloului.

51
00:02:47,280 --> 00:02:51,090
În caz contrar, vom căuta
partea dreapta a matrice.

52
00:02:51,090 --> 00:02:54,410
Iar la final, dacă nu aveți nici o
mai multe elemente de stânga pentru a căuta, dar te

53
00:02:54,410 --> 00:02:58,050
Nu s-au găsit acul încă, atunci
return false deoarece acul

54
00:02:58,050 --> 00:03:01,890
cu siguranta nu este în carul cu fân.

55
00:03:01,890 --> 00:03:05,270
>> Acum, un lucru elegant despre acest pseudocod
în binar de căutare este că acesta poate fi

56
00:03:05,270 --> 00:03:09,940
interpretat fie ca o iterativ
sau punerea în aplicare a recursiv.

57
00:03:09,940 --> 00:03:13,810
Asa ca ar fi recursiv, dacă te-a sunat
funcția de căutare în căutarea

58
00:03:13,810 --> 00:03:17,350
funcționeze pe fiecare jumătate de matrice.

59
00:03:17,350 --> 00:03:21,030
Vom acoperi recursivitate un pic mai târziu, în
Desigur, dar știu că aceasta este o

60
00:03:21,030 --> 00:03:24,190
opțiune dacă doriți să încercați.

61
00:03:24,190 --> 00:03:26,030
>> Acum, să ne uităm la fel.

62
00:03:26,030 --> 00:03:30,750
Un fel nevoie de o matrice și întreg
n, care este dimensiunea matricii.

63
00:03:30,750 --> 00:03:34,030
Acum, există diferite tipuri diferite
de soiuri, si poti sa te uiti la unele

64
00:03:34,030 --> 00:03:36,370
pantaloni scurți pentru demo-uri și explicații.

65
00:03:36,370 --> 00:03:39,580
Tipul de retur pentru noastră
Funcția de sortare este nulă.

66
00:03:39,580 --> 00:03:43,580
Asta înseamnă că nu vom
pentru a reveni orice matrice de la fel.

67
00:03:43,580 --> 00:03:48,140
Suntem de fapt de gând să schimbe foarte
matrice care a fost trecut în noi.

68
00:03:48,140 --> 00:03:52,290
>> Și asta e posibil, deoarece matrice sunt
transmise prin referință în C. Acum vom

69
00:03:52,290 --> 00:03:55,290
a se vedea mai multe despre acest lucru mai târziu, dar
diferență esențială între trecere

70
00:03:55,290 --> 00:03:59,340
în ceva ca un întreg și trecere
într-o matrice, este că atunci când

71
00:03:59,340 --> 00:04:03,490
trece într-un întreg, C este doar de gând să
face o copie de care întreg și să treacă

72
00:04:03,490 --> 00:04:04,450
acesta a funcției.

73
00:04:04,450 --> 00:04:08,530
Variabila originală nu va fi modificată
odată ce funcția este terminat.

74
00:04:08,530 --> 00:04:12,480
Cu o serie, pe de altă parte, este
nu de gând să facă o copie, și veți

75
00:04:12,480 --> 00:04:17,910
de fapt, să fie editarea
foarte matrice în sine.

76
00:04:17,910 --> 00:04:21,269
>> Deci, un tip de sortare este
un fel de selecție.

77
00:04:21,269 --> 00:04:24,750
Un fel de selecție de lucrări pornind de la
la început, și apoi voi repeta

78
00:04:24,750 --> 00:04:26,820
peste și pentru a găsi cel mai mic element.

79
00:04:26,820 --> 00:04:30,710
Și apoi de swap, care mai mic
Element cu prima.

80
00:04:30,710 --> 00:04:34,360
Și apoi trece la al doilea element
, A găsi cele mai mici următoare

81
00:04:34,360 --> 00:04:38,320
elemente, și apoi de swap că, odată cu
al doilea element în matrice deoarece

82
00:04:38,320 --> 00:04:41,100
Primul element este deja sortat.

83
00:04:41,100 --> 00:04:45,370
Și așa, atunci veți continua pentru fiecare
Element în identificarea mai mici

84
00:04:45,370 --> 00:04:47,690
valoare și schimbarea l.

85
00:04:47,690 --> 00:04:53,460
>> Pentru I este egal cu 0, foarte primul element
a n minus 1, ai de gând să compare

86
00:04:53,460 --> 00:04:57,820
fiecare următor valoare, după care și găsească
indicele de valoarea minimă.

87
00:04:57,820 --> 00:05:02,520
Odată ce ați găsit indicele valorii minime,
puteți schimba această valoare de matrice

88
00:05:02,520 --> 00:05:05,930
minim și matrice I.

89
00:05:05,930 --> 00:05:09,760
>> Un alt tip de fel pe care le puteți
să pună în aplicare este balon fel.

90
00:05:09,760 --> 00:05:14,380
Deci reiterează bule de sortare peste lista
comparând elementele adiacente și

91
00:05:14,380 --> 00:05:17,720
schimbarea elementelor care
sunt în ordine greșită.

92
00:05:17,720 --> 00:05:22,380
Și în acest fel, cel mai mare element
va bule până la capăt.

93
00:05:22,380 --> 00:05:28,070
Și lista este sortată o dată nu mai
elemente au fost schimbate.

94
00:05:28,070 --> 00:05:31,920
>> Deci, acestea sunt două exemple de fel
algoritmi pe care le puteți pune în aplicare pentru

95
00:05:31,920 --> 00:05:33,230
programul de descoperire.

96
00:05:33,230 --> 00:05:37,350
După ce ați terminat de sortare, și ai
făcut de căutare, ați terminat.

97
00:05:37,350 --> 00:05:39,720
Numele meu este Zamyla, iar acest lucru este CS50.

98
00:05:39,720 --> 00:05:46,987
>> [Redare a muzicii]