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

2
00:00:13,300 --> 00:00:15,010
>> Rob Bowden: Hi, unë jam Rob.

3
00:00:15,010 --> 00:00:16,790
Si mund ne të punësojë një kërkim binar?

4
00:00:16,790 --> 00:00:18,770
Le të gjeni.

5
00:00:18,770 --> 00:00:23,400
Pra, vini re se këtë kërkim ne jemi duke shkuar
për të zbatuar Recursively.

6
00:00:23,400 --> 00:00:27,470
Ju gjithashtu mund të zbatojë kërko binar
iteratively, kështu që nëse ju e bëri këtë,

7
00:00:27,470 --> 00:00:29,280
kjo është përsosmërisht mirë.

8
00:00:29,280 --> 00:00:32,820
>> Tani pari, le të mbani mend se çfarë
Parametrat në kërkim janë menduar të jetë.

9
00:00:32,820 --> 00:00:36,120
Këtu, ne shohim vlera int, e cila është
menduar të jetë vlera e përdoruesit është

10
00:00:36,120 --> 00:00:37,320
kërkoni për.

11
00:00:37,320 --> 00:00:40,800
Ne e shohim array vlerave int, e cila
është grup në të cilin ne jemi

12
00:00:40,800 --> 00:00:42,520
kërkoni për vlerën.

13
00:00:42,520 --> 00:00:45,602
Dhe ne shohim int n, e cila është
gjatësia e array tonë.

14
00:00:45,602 --> 00:00:47,410
>> Tani, gjëja e parë e parë.

15
00:00:47,410 --> 00:00:51,350
Ne kontrolloni për të parë nëse n është e barabartë me 0, në
cilin rast ne e kthimit të rreme.

16
00:00:51,350 --> 00:00:54,770
Kjo është vetëm duke thënë se në qoftë se ne kemi një bosh
array, vlera nuk është e qartë në një

17
00:00:54,770 --> 00:00:57,860
array bosh, kështu që ne mund të kthimit të rreme.

18
00:00:57,860 --> 00:01:01,250
>> Tani, ne të vërtetë duan të bëjnë binare
kërko pjesë e kërkimit binar.

19
00:01:01,250 --> 00:01:04,780
Pra, ne duam të gjetur në qendër
element i kësaj grup.

20
00:01:04,780 --> 00:01:09,130
Këtu, të themi të mesëm është e barabartë me n ndarë
me 2, pasi elementi mesme është

21
00:01:09,130 --> 00:01:12,240
do të jenë gjatësia e
koleksion tona i ndarë me 2.

22
00:01:12,240 --> 00:01:15,040
Tani ne jemi duke shkuar për të kontrolluar për të parë nëse
element të mesëm është e barabartë me vlerën që jeni

23
00:01:15,040 --> 00:01:16,160
kërkoni për.

24
00:01:16,160 --> 00:01:21,030
Pra, nëse vlerat e mesme është e barabartë me vlerën, ne
mund të kthehet e vërtetë që kemi gjetur

25
00:01:21,030 --> 00:01:22,810
Vlera në grup tonë.

26
00:01:22,810 --> 00:01:26,380
>> Por në qoftë se kjo nuk ishte e vërtetë, tani
ne kemi nevojë për të bërë gjithkund rekursive

27
00:01:26,380 --> 00:01:27,840
hap e kërkimit binar.

28
00:01:27,840 --> 00:01:30,450
Ne kemi nevojë për të kërkuar ose për të
majtë të array ose për të

29
00:01:30,450 --> 00:01:32,320
mes të vektorit.

30
00:01:32,320 --> 00:01:39,280
Kështu që këtu, të themi nëse vlerat në mes është
më pak se vlera, që do të thotë se vlera

31
00:01:39,280 --> 00:01:41,350
ishte më e madhe sesa mes
e array.

32
00:01:41,350 --> 00:01:45,790
Pra, vlera duhet të jetë në të djathtë të
element që ne vetëm shikuar.

33
00:01:45,790 --> 00:01:48,090
>> Pra këtu, ne do të
kërko Recursively.

34
00:01:48,090 --> 00:01:50,320
Dhe ne do të shikojmë se çfarë ne jemi duke kaluar
për këtë në një të dytë.

35
00:01:50,320 --> 00:01:53,440
Por ne jemi duke shkuar për të kërkuar të
drejtën e elementit mesme.

36
00:01:53,440 --> 00:01:57,710
Dhe në rastin tjetër, kjo do të thotë se
Vlera ishte më pak se mesi i

37
00:01:57,710 --> 00:02:00,660
array, dhe kështu që ne jemi duke shkuar
për të kërkuar në të majtë.

38
00:02:00,660 --> 00:02:03,520
Tani, e majta do të jetë
pak më e lehtë për të parë.

39
00:02:03,520 --> 00:02:07,770
Pra, ne shohim këtu se ne jemi Recursively
duke e quajtur kërko ku i pari

40
00:02:07,770 --> 00:02:10,120
Argumenti është, përsëri, vlera
ne jemi duke kërkuar mbi të.

41
00:02:10,120 --> 00:02:14,970
Argumenti dytë do të jenë
array se ne ishim në kërkim gjatë.

42
00:02:14,970 --> 00:02:17,090
Dhe elementi i fundit tani është e mesme.

43
00:02:17,090 --> 00:02:21,650
Mos harroni parametri i fundit është int ynë
n, kështu që është gjatësia e rrjet të.

44
00:02:21,650 --> 00:02:25,310
>> Në thirrjen gjithkund rekursive për të kërkuar, ne jemi
tani duke thënë se gjatësia e

45
00:02:25,310 --> 00:02:27,230
array është e mesme.

46
00:02:27,230 --> 00:02:32,900
Pra, nëse koleksion tona ishte i madhësisë 20 dhe ne
kontrolluar në indeksin 10, pasi e mesme është

47
00:02:32,900 --> 00:02:36,930
20 ndarë nga 2, që do të thotë ne jemi
duke kaluar 10 si i ri

48
00:02:36,930 --> 00:02:38,300
Gjatësia e array tonë.

49
00:02:38,300 --> 00:02:41,910
Mos harroni se kur ju keni një rrjet të
e gjatësi 10, që do të thotë të vlefshme

50
00:02:41,910 --> 00:02:45,450
elemente janë në indekset 0 deri në 9.

51
00:02:45,450 --> 00:02:50,120
Pra, kjo është pikërisht ajo që ne duam të
specifikoni grup tonë të përditësuar - e majtë

52
00:02:50,120 --> 00:02:53,010
grup nga elementi mesme.

53
00:02:53,010 --> 00:02:55,710
>> Pra, duke kërkuar në të djathtë është
pak më e vështirë.

54
00:02:55,710 --> 00:03:00,170
Tani pari, le të marrë në konsideratë gjatësinë
i array për të drejtën e

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

56
00:03:01,240 --> 00:03:08,390
Pra, nëse koleksion tona ishte i madhësisë n, atëherë
Grup i ri do të jetë i madhësisë n minus

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

58
00:03:10,140 --> 00:03:12,530
Pra, le të mendojnë për n minus qëndër.

59
00:03:12,530 --> 00:03:18,710
>> Përsëri, në qoftë se array ishin të madhësisë 20 dhe
ne ndani me 2 për të marrë e mesme,

60
00:03:18,710 --> 00:03:23,540
kështu e mesme është 10, atëherë n minus mesme
do të na japë 10, kështu që 10

61
00:03:23,540 --> 00:03:25,330
elementet në të djathtë e mesme.

62
00:03:25,330 --> 00:03:27,780
Por ne gjithashtu kemi këtë minus
1, pasi ne nuk duam të

63
00:03:27,780 --> 00:03:29,700
përfshijnë në qendër vetë.

64
00:03:29,700 --> 00:03:34,190
Pra, n minus mesme minus 1 na jep
Numri i përgjithshëm i elementeve të së drejtës

65
00:03:34,190 --> 00:03:36,800
i indeksit mesme në vektorit.

66
00:03:36,800 --> 00:03:41,870
>> Tani këtu, mos harroni se e mesme
parametër është array vlerat.

67
00:03:41,870 --> 00:03:46,180
Pra këtu, ne jemi duke kaluar një
Rifreskimi Vlerat array.

68
00:03:46,180 --> 00:03:50,930
Kjo vlerat plus plus mesme 1 është
në të vërtetë duke thënë Recursively telefononi

69
00:03:50,930 --> 00:03:56,460
kërko, duke kaluar në një rrjet të ri, ku
që grup i ri fillon në mes

70
00:03:56,460 --> 00:03:59,370
plus një nga vlerat origjinale array tonë.

71
00:03:59,370 --> 00:04:05,400
>> Një sintaksë alternative për këtë, tani që
ju keni filluar të shihni pointers, është

72
00:04:05,400 --> 00:04:10,170
Vlerat ampersand plus mesme 1.

73
00:04:10,170 --> 00:04:17,149
Pra, kap adresën e mes
plus një element i vlerave.

74
00:04:17,149 --> 00:04:23,690
>> Tani, në qoftë se nuk keni qenë të rehatshme
modifikuar një rrjet të tillë, ju

75
00:04:23,690 --> 00:04:28,900
gjithashtu do të mund të zbatohet duke përdorur këtë
një funksion recursive ndihmës, ku

76
00:04:28,900 --> 00:04:31,680
se funksioni ndihmës merr
më shumë argumente.

77
00:04:31,680 --> 00:04:36,610
Pra, në vend që të marrë vetëm vlerën,
array, dhe madhësia e array,

78
00:04:36,610 --> 00:04:42,315
funksioni i ndihmës mund të marrë më shumë
argumente, duke përfshirë indeksin më të ulët

79
00:04:42,315 --> 00:04:45,280
se ju do të kujdeseni për në rrjet
dhe indeksi sipërme që ju kujdeseni

80
00:04:45,280 --> 00:04:46,300
rreth array.

81
00:04:46,300 --> 00:04:49,770
>> Dhe kështu që mbajtja e dy më të ulët
Indeksi dhe indeksi sipërme, ju nuk e bëni

82
00:04:49,770 --> 00:04:52,780
nevojë për të kurrë të modifikuar
Vlerat origjinale array.

83
00:04:52,780 --> 00:04:56,390
Ju vetëm mund të vazhdojë të
përdorni array vlerat.

84
00:04:56,390 --> 00:04:59,540
Por këtu, vini re ne nuk kemi nevojë për një ndihmës
funksionojë për sa kohë që ne jemi

85
00:04:59,540 --> 00:05:01,760
të gatshëm për të modifikuar origjinal
Vlerat array.

86
00:05:01,760 --> 00:05:05,020
Ne jemi të gatshëm për të kaluar në
një vlerat updated.

87
00:05:05,020 --> 00:05:09,140
>> Tani, ne nuk mund të kërko binar mbi
një grup që është unsorted.

88
00:05:09,140 --> 00:05:12,220
Pra, le të marrë këtë ndahen.

89
00:05:12,220 --> 00:05:17,650
Tani, vini re se lloj është e kaluara dy
parametrat int vlerat, e cila është

90
00:05:17,650 --> 00:05:21,110
array se ne jemi klasifikim, dhe int n,
cila është gjatësia e vektorit që

91
00:05:21,110 --> 00:05:22,250
ne jemi zgjidhja.

92
00:05:22,250 --> 00:05:24,840
Pra, këtu ne duam të zbatojë
një algorithm sorting

93
00:05:24,840 --> 00:05:26,690
qe eshte o i N katror.

94
00:05:26,690 --> 00:05:30,560
Ju mund të zgjidhni flluskë renditjeje, përzgjedhje
lloj, apo futje lloj, ose

95
00:05:30,560 --> 00:05:32,670
një lloj tjetër ne nuk kemi
shihet në klasë.

96
00:05:32,670 --> 00:05:36,380
Por këtu, ne do të
përdorni përzgjedhjes lloj.

97
00:05:36,380 --> 00:05:40,030
>> Pra, ne do të iterate
mbi gjithë array.

98
00:05:40,030 --> 00:05:44,360
E pra, këtu ne shohim se ne jemi iterating
nga 0 deri n minus 1.

99
00:05:44,360 --> 00:05:45,990
Pse jo të gjithë rrugën deri në n?

100
00:05:45,990 --> 00:05:49,320
E pra, në qoftë se ne kemi renditur tashmë e parë
n minus 1 elemente, atëherë

101
00:05:49,320 --> 00:05:54,420
element shumë të fundit ajo që duhet tashmë të jenë të
në vendin e duhur, në mënyrë klasifikim mbi

102
00:05:54,420 --> 00:05:56,520
tërë array.

103
00:05:56,520 --> 00:05:58,770
>> Tani, mos harroni se si përzgjedhja
lloj punon.

104
00:05:58,770 --> 00:06:01,950
Ne jemi duke shkuar për të shkuar në të gjithë array
duke kërkuar për vlerën minimale në

105
00:06:01,950 --> 00:06:04,480
array dhe të ngjit që
në fillim.

106
00:06:04,480 --> 00:06:07,610
Pastaj ne jemi duke shkuar për të shkuar në të gjithë
array përsëri në kërkim të dytë

107
00:06:07,610 --> 00:06:10,410
element më i vogël, dhe të ngjit që
në pozicionin e dytë në

108
00:06:10,410 --> 00:06:12,100
array, dhe kështu me radhë.

109
00:06:12,100 --> 00:06:14,330
Pra, kjo është ajo që kjo është duke bërë.

110
00:06:14,330 --> 00:06:17,290
>> Këtu, ne jemi duke parë se ne jemi
vendosjen minimale aktuale

111
00:06:17,290 --> 00:06:20,030
vlerë të indeksit i-th.

112
00:06:20,030 --> 00:06:23,160
Pra, në përsëritje të parë, ne jemi duke shkuar
të marrin në konsideratë vlera minimale që të jetë e

113
00:06:23,160 --> 00:06:25,030
fillimi i array tonë.

114
00:06:25,030 --> 00:06:28,500
Pastaj, ne do të iterate mbi
Pjesa tjetër e array, duke kontrolluar të

115
00:06:28,500 --> 00:06:31,870
të parë nëse ka ndonjë elemente të vogla se
ai që ne jemi aktualisht

116
00:06:31,870 --> 00:06:33,900
konsideruar minimale.

117
00:06:33,900 --> 00:06:38,840
>> Kështu që këtu, vlerat j plus një të tillë - kjo është
më pak se ajo që ne jemi aktualisht

118
00:06:38,840 --> 00:06:40,380
konsideruar minimale.

119
00:06:40,380 --> 00:06:42,940
Pastaj ne jemi duke shkuar për të rinovuar atë
ne mendojmë se është minimale për të

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

121
00:06:44,640 --> 00:06:48,540
Pra, bëni atë në të gjithë grup,
dhe pas kësaj për loop, minimale

122
00:06:48,540 --> 00:06:53,160
duhet të jetë element minimale nga
Pozicioni i-th në rrjet.

123
00:06:53,160 --> 00:06:57,350
>> Pasi që kemi, ne mund të bie në ujdi
Vlera minimale në pozicionin i-

124
00:06:57,350 --> 00:06:58,230
në rrjet.

125
00:06:58,230 --> 00:07:00,130
Pra, kjo është vetëm një shkëmbim standarde.

126
00:07:00,130 --> 00:07:03,940
Ne dyqan në një vlerë të përkohshëm -
vlera i-th në rrjet -

127
00:07:03,940 --> 00:07:08,460
vënë në vlerën e i-të në grup
Vlera minimale që i takon atje,

128
00:07:08,460 --> 00:07:13,580
dhe pastaj dyqan përsëri në ku
vlera aktuale minimale përdoret për të

129
00:07:13,580 --> 00:07:16,460
Vlera i-th në rrjet, në mënyrë
se ne nuk kemi humbur atë.

130
00:07:16,460 --> 00:07:20,510
>> Pra, që vazhdon në
Përsëritje e ardhshme.

131
00:07:20,510 --> 00:07:23,480
Ne do të fillojmë të shikojmë për të dytë
Vlera minimale dhe futur që në

132
00:07:23,480 --> 00:07:24,590
Pozita e dytë.

133
00:07:24,590 --> 00:07:27,440
Në përsëritje të tretë, ne do të shikojmë për
Vlera minimale e tretë dhe të futur

134
00:07:27,440 --> 00:07:31,550
që në pozicionin e tretë, dhe kështu
deri sa ne kemi një rrjet të renditura.

135
00:07:31,550 --> 00:07:33,820
Emri im është Rob, dhe kjo
ishte zgjedhja lloj.

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