1
00:00:00,000 --> 00:00:13,300

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Bună, eu sunt Rob.

3
00:00:15,010 --> 00:00:16,790
Cum putem folosi o căutare binar?

4
00:00:16,790 --> 00:00:18,770
Haideți să aflăm.

5
00:00:18,770 --> 00:00:23,400
Deci, rețineți că această căutare vom
pentru punerea în aplicare recursiv.

6
00:00:23,400 --> 00:00:27,470
Ai putea să pună în aplicare, de asemenea, de căutare binară
iterativ, așa că, dacă ai făcut asta,

7
00:00:27,470 --> 00:00:29,280
asta e foarte bine.

8
00:00:29,280 --> 00:00:32,820
>> Acum, în primul rând, să ne amintim ceea ce
parametri de căutare sunt menite să fie.

9
00:00:32,820 --> 00:00:36,120
Aici, vom vedea valoare int, care este
ar trebui să fie valoarea utilizatorul este

10
00:00:36,120 --> 00:00:37,320
căutați.

11
00:00:37,320 --> 00:00:40,800
Vedem matrice valori int, care
este matrice în care suntem

12
00:00:40,800 --> 00:00:42,520
în căutare de valoare.

13
00:00:42,520 --> 00:00:45,602
Și vom vedea int n, care este
lungimea matrice noastre.

14
00:00:45,602 --> 00:00:47,410
>> Acum, primul lucru primul.

15
00:00:47,410 --> 00:00:51,350
Vom verifica pentru a vedea dacă n este egal cu 0, în
caz în care ne vom întoarce false.

16
00:00:51,350 --> 00:00:54,770
Asta e doar că dacă avem un gol
matrice, o valoare nu este în mod clar într-o

17
00:00:54,770 --> 00:00:57,860
array gol, astfel încât să putem întoarce false.

18
00:00:57,860 --> 00:01:01,250
>> Acum, am de fapt vrei sa faci binar
Cautare parte din căutare binare.

19
00:01:01,250 --> 00:01:04,780
Deci, ne-o dorim pentru a găsi mijlocul
element al acestei matrice.

20
00:01:04,780 --> 00:01:09,130
Aici, noi spunem de mijloc este egal cu n împărțit
de 2, întrucât elementul din mijloc este

21
00:01:09,130 --> 00:01:12,240
Va fi lungimea
gama noastră împărțit la 2.

22
00:01:12,240 --> 00:01:15,040
Acum vom verifica pentru a vedea dacă
elementul din mijloc este egal cu valoarea suntem

23
00:01:15,040 --> 00:01:16,160
căutați.

24
00:01:16,160 --> 00:01:21,030
Deci, dacă valorile de mijloc este egal cu valoare, avem
poate reveni adevărat, deoarece am găsit

25
00:01:21,030 --> 00:01:22,810
valoare în gama noastră.

26
00:01:22,810 --> 00:01:26,380
>> Dar în cazul în care nu era adevărat, acum
avem nevoie pentru a face recursiv

27
00:01:26,380 --> 00:01:27,840
pas de căutare binare.

28
00:01:27,840 --> 00:01:30,450
Avem nevoie de a căuta fie la
a plecat de matrice sau la

29
00:01:30,450 --> 00:01:32,320
mijloc de matrice.

30
00:01:32,320 --> 00:01:39,280
Deci, aici, ne spune dacă valorile de la mijloc este
mai puțin decât valoarea, ceea ce înseamnă că valoarea

31
00:01:39,280 --> 00:01:41,350
a fost mai mare decât la mijloc
de matrice.

32
00:01:41,350 --> 00:01:45,790
Deci, valoarea trebuie să fie de dreapta a
element care ne-am uitat la.

33
00:01:45,790 --> 00:01:48,090
>> Deci, aici, vom
căutare recursiv.

34
00:01:48,090 --> 00:01:50,320
Și ne vom uita la ceea ce ne trece
la aceasta într-o secundă.

35
00:01:50,320 --> 00:01:53,440
Dar vom căuta la
dreapta a elementului de mijloc.

36
00:01:53,440 --> 00:01:57,710
Și în celălalt caz, ceea ce înseamnă că
valoare a fost mai mică decât la mijlocul

37
00:01:57,710 --> 00:02:00,660
matrice, și așa vom
pentru a căuta spre stânga.

38
00:02:00,660 --> 00:02:03,520
Acum, stânga va fi
un pic mai ușor să se uite la.

39
00:02:03,520 --> 00:02:07,770
Deci, vedem aici că suntem recursiv
de asteptare de căutare în cazul în care primul

40
00:02:07,770 --> 00:02:10,120
argument este, din nou, valoarea
căutăm peste.

41
00:02:10,120 --> 00:02:14,970
Al doilea argument va fi
matrice care ne-au fost căutați peste.

42
00:02:14,970 --> 00:02:17,090
Și ultimul element este acum de mijloc.

43
00:02:17,090 --> 00:02:21,650
Amintiți-vă de ultimul parametru este int nostru
n, așa că e lungimea de matrice noastre.

44
00:02:21,650 --> 00:02:25,310
>> În apelul recursiv pentru a căuta, suntem
acum spunând că lungimea

45
00:02:25,310 --> 00:02:27,230
matrice este de mijloc.

46
00:02:27,230 --> 00:02:32,900
Deci, în cazul în care gama noastră era de mărimea 20 și ne-am
căutat la index de 10, deoarece de mijloc este

47
00:02:32,900 --> 00:02:36,930
20 împărțit la 2, înseamnă că suntem
trecerea 10 ca noul

48
00:02:36,930 --> 00:02:38,300
lungime de matrice noastre.

49
00:02:38,300 --> 00:02:41,910
Amintiți-vă că atunci când aveți o matrice
de lungime 10, ceea ce înseamnă că valabil

50
00:02:41,910 --> 00:02:45,450
elemente sunt în indici de la 0 la 9.

51
00:02:45,450 --> 00:02:50,120
Deci, asta este exact ceea ce vrem să
specifica gama noastră actualizare - stânga

52
00:02:50,120 --> 00:02:53,010
matrice de elementul de mijloc.

53
00:02:53,010 --> 00:02:55,710
>> Deci, în căutarea de la dreapta este
un pic mai dificil.

54
00:02:55,710 --> 00:03:00,170
Acum, în primul rând, să ia în considerare lungimea
de matrice la dreapta a

55
00:03:00,170 --> 00:03:01,240
element de mijloc.

56
00:03:01,240 --> 00:03:08,390
Deci, în cazul în gama noastră a fost de dimensiune n, atunci
Noua matrice va fi de dimensiune n minus

57
00:03:08,390 --> 00:03:10,140
minus mijloc 1.

58
00:03:10,140 --> 00:03:12,530
Deci, haideți să ne gândim de n minus de mijloc.

59
00:03:12,530 --> 00:03:18,710
>> Din nou, în cazul în matrice au fost de mărime 20 și
vom împărți cu 2 pentru a obține mijloc,

60
00:03:18,710 --> 00:03:23,540
astfel încât la mijloc este de 10, atunci n minus de mijloc
este de gând să ne dea 10, deci 10

61
00:03:23,540 --> 00:03:25,330
elemente de la dreptul de mijloc.

62
00:03:25,330 --> 00:03:27,780
Dar avem, de asemenea, acest minus
1, deoarece nu vrem să

63
00:03:27,780 --> 00:03:29,700
includ mijloc în sine.

64
00:03:29,700 --> 00:03:34,190
Deci, n minus de mijloc minus 1 ne dă
numărul total de elemente de la dreapta

65
00:03:34,190 --> 00:03:36,800
indicelui de mijloc în matrice.

66
00:03:36,800 --> 00:03:41,870
>> Acum, aici, amintiți-vă că la mijloc
parametru este array valori.

67
00:03:41,870 --> 00:03:46,180
Deci, aici, vom trece un
actualizat valori matrice.

68
00:03:46,180 --> 00:03:50,930
Aceste valori, plus plus de mijloc 1 este
de fapt spunând apel recursiv

69
00:03:50,930 --> 00:03:56,460
căutare, trecerea într-o nouă matrice, în cazul în care
că noua matrice începe în mijloc

70
00:03:56,460 --> 00:03:59,370
plus una din valorile originale gama noastră.

71
00:03:59,370 --> 00:04:05,400
>> O sintaxă alternativă pentru că, acum că
ați început să vadă indicii, este

72
00:04:05,400 --> 00:04:10,170
Valorile ampersand plus de mijloc 1.

73
00:04:10,170 --> 00:04:17,149
Deci, apuca adresa de mijloc
plus un element de valori.

74
00:04:17,149 --> 00:04:23,690
>> Acum, dacă nu sunt confortabile
modificarea o matrice de genul asta, ai

75
00:04:23,690 --> 00:04:28,900
de asemenea, ar putea fi pus în aplicare acest lucru utilizând
o functie helper recursiv, unde

76
00:04:28,900 --> 00:04:31,680
că funcția helper ia
mai multe argumente.

77
00:04:31,680 --> 00:04:36,610
Deci, în loc de a lua doar valoarea,
matrice, și dimensiunea matricii,

78
00:04:36,610 --> 00:04:42,315
funcția de ajutor ar putea lua mai mult
argumente, inclusiv indicele inferior

79
00:04:42,315 --> 00:04:45,280
care le-ar pasa de la matrice
și indicele de sus ca iti pasa

80
00:04:45,280 --> 00:04:46,300
despre matrice.

81
00:04:46,300 --> 00:04:49,770
>> Și așa a ține evidența atât de jos
index și indicele de sus, tu nu faci

82
00:04:49,770 --> 00:04:52,780
necesitatea de a modifica oricând
valorile originale matrice.

83
00:04:52,780 --> 00:04:56,390
Puteți continua doar pentru a
folosi matrice valori.

84
00:04:56,390 --> 00:04:59,540
Dar aici, observa nu avem nevoie de un ajutor
funcționează atâta timp cât suntem

85
00:04:59,540 --> 00:05:01,760
dispus să modifice originalul
Valorile matrice.

86
00:05:01,760 --> 00:05:05,020
Suntem dispuși să treacă în
un valori actualizate.

87
00:05:05,020 --> 00:05:09,140
>> Acum, nu putem binar de căutare pe
o matrice care este nesortate.

88
00:05:09,140 --> 00:05:12,220
Deci, hai să sortate.

89
00:05:12,220 --> 00:05:17,650
Acum, observați că este un fel trecut două
Parametrii int valori, care este

90
00:05:17,650 --> 00:05:21,110
matrice care suntem sortarea, și int n,
care este lungimea unui array care

91
00:05:21,110 --> 00:05:22,250
suntem de sortare.

92
00:05:22,250 --> 00:05:24,840
Deci, aici vrem să pună în aplicare
un algoritm de sortare

93
00:05:24,840 --> 00:05:26,690
adică o de n pătrat.

94
00:05:26,690 --> 00:05:30,560
Ai putea alege cu bule de sortare, selectare
un fel, sau inserare fel, sau

95
00:05:30,560 --> 00:05:32,670
un alt fel noi nu avem
văzut în clasă.

96
00:05:32,670 --> 00:05:36,380
Dar aici, vom
folosesc selecție de sortare.

97
00:05:36,380 --> 00:05:40,030
>> Deci, vom repeta
pentru întreaga rețea.

98
00:05:40,030 --> 00:05:44,360
Ei bine, aici vom vedea că suntem iterarea
de la 0 la n minus 1.

99
00:05:44,360 --> 00:05:45,990
De ce nu tot drumul până la n?

100
00:05:45,990 --> 00:05:49,320
Ei bine, dacă ne-am sortate deja primul
n minus 1 elemente, apoi

101
00:05:49,320 --> 00:05:54,420
ultimul element de care trebuie să fie deja
în locul corect, așa sortare peste

102
00:05:54,420 --> 00:05:56,520
întreaga rețea.

103
00:05:56,520 --> 00:05:58,770
>> Acum, amintiți-vă cât de selecție
un fel de lucrări.

104
00:05:58,770 --> 00:06:01,950
Vom merge pentru întreaga rețea,
în căutarea pentru valoarea minimă în

105
00:06:01,950 --> 00:06:04,480
matrice și stick-ul care
la început.

106
00:06:04,480 --> 00:06:07,610
Apoi vom trece peste întreaga
matrice din nou în căutarea pentru a doua

107
00:06:07,610 --> 00:06:10,410
mai mic element, și băț că
în cea de a doua poziție în

108
00:06:10,410 --> 00:06:12,100
matrice, și așa mai departe.

109
00:06:12,100 --> 00:06:14,330
Deci, asta e ceea ce acest lucru este de a face.

110
00:06:14,330 --> 00:06:17,290
>> Aici, vedem că suntem
stabilirea minim actual

111
00:06:17,290 --> 00:06:20,030
valoare a indicelui i-lea.

112
00:06:20,030 --> 00:06:23,160
Deci, pe prima iterație, vom
să ia în considerare valoarea minimă a fi

113
00:06:23,160 --> 00:06:25,030
începutul matrice noastre.

114
00:06:25,030 --> 00:06:28,500
Apoi, vom repeta de-a lungul
restul de matrice, de verificare a

115
00:06:28,500 --> 00:06:31,870
a se vedea dacă există orice elemente mai mici decât
cel pe care suntem în prezent

116
00:06:31,870 --> 00:06:33,900
considerând minim.

117
00:06:33,900 --> 00:06:38,840
>> Deci, aici, valorile j plus una - care este
mai puțin decât ceea ce sunt în prezent

118
00:06:38,840 --> 00:06:40,380
considerând minim.

119
00:06:40,380 --> 00:06:42,940
Apoi, vom actualiza ceea ce
noi credem ca este minim a

120
00:06:42,940 --> 00:06:44,640
index j plus 1.

121
00:06:44,640 --> 00:06:48,540
Deci, nu că pe întreaga rețea,
și după aceasta pentru buclă, minim

122
00:06:48,540 --> 00:06:53,160
ar fi elementul minim din
poziția i-lea în matrice.

123
00:06:53,160 --> 00:06:57,350
>> După ce ne-am asta, putem schimba
Valoarea minimă în poziția i-lea

124
00:06:57,350 --> 00:06:58,230
în matrice.

125
00:06:58,230 --> 00:07:00,130
Deci, aceasta este doar un schimb standard.

126
00:07:00,130 --> 00:07:03,940
Stocăm într-o valoare temporar -
valoarea i-lea în matrice -

127
00:07:03,940 --> 00:07:08,460
pune în valoare i-lea în matrice
Valoarea minimă care aparține acolo,

128
00:07:08,460 --> 00:07:13,580
și apoi depozitați înapoi în cazul în care
Valoarea minimă de curent folosit pentru a fi

129
00:07:13,580 --> 00:07:16,460
i-lea valoare în matrice, așa
pe care nu l-am pierdut.

130
00:07:16,460 --> 00:07:20,510
>> Deci, care continuă pe
urmatoarea iteratie.

131
00:07:20,510 --> 00:07:23,480
Vom începe căutarea pentru al doilea
valoarea minimă și introduceți că în

132
00:07:23,480 --> 00:07:24,590
a doua poziție.

133
00:07:24,590 --> 00:07:27,440
La a treia repetare, ne vom uita pentru
a treia valoarea minimă și inserția

134
00:07:27,440 --> 00:07:31,550
care în poziția a treia, și așa
pe până când vom avea un tablou sortat.

135
00:07:31,550 --> 00:07:33,820
Numele meu este Rob, și acest lucru
a fost un fel de selecție.

136
00:07:33,820 --> 00:07:39,456