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

2
00:00:13,300 --> 00:00:15,010
>> ROB Bowden: Saluton, mi estas Rob.

3
00:00:15,010 --> 00:00:16,790
Kiel ni dungi duuma serĉo?

4
00:00:16,790 --> 00:00:18,770
Ni ekscias.

5
00:00:18,770 --> 00:00:23,400
Do atentu, ke tiu serĉo ni iras
apliki rekursie.

6
00:00:23,400 --> 00:00:27,470
Vi povus ankaŭ apliki duuma serĉo
ripete, do se vi faris tion,

7
00:00:27,470 --> 00:00:29,280
tio estas perfekte bone.

8
00:00:29,280 --> 00:00:32,820
>> Nun unue, ni memoru, kion la
parametroj por serĉo celas esti.

9
00:00:32,820 --> 00:00:36,120
Tie, ni vidas int valoro, kiu estas
supozitaj esti la valoro de la uzanto estas

10
00:00:36,120 --> 00:00:37,320
serĉi.

11
00:00:37,320 --> 00:00:40,800
Ni vidas la int valoroj tabelo, kiu
estas la tabelo en kiu ni estas

12
00:00:40,800 --> 00:00:42,520
serĉas valoron.

13
00:00:42,520 --> 00:00:45,602
Kaj ni vidos int n, kiu estas
la longo de nia tabelo.

14
00:00:45,602 --> 00:00:47,410
>> Nun, unua afero unue.

15
00:00:47,410 --> 00:00:51,350
Ni kontrolu se n egalas 0, en
tiaokaze ni revenos falsaj.

16
00:00:51,350 --> 00:00:54,770
Tio nur diras, se ni havas malplenan
tabelo, valoro estas klare ne en

17
00:00:54,770 --> 00:00:57,860
malplena tabelo, do ni povas reveni falsaj.

18
00:00:57,860 --> 00:01:01,250
>> Nun, ni efektive deziras fari la duuma
search parto de duuma serĉo.

19
00:01:01,250 --> 00:01:04,780
Do, ni volas trovi la mezo
ero de tiu tabelo.

20
00:01:04,780 --> 00:01:09,130
Tie, ni diru mezo egalas n dividita
per 2, ekde la meza elemento estas

21
00:01:09,130 --> 00:01:12,240
tuj estos la longeco de
nia tabelo dividite per 2.

22
00:01:12,240 --> 00:01:15,040
Nun ni iras por kontroli, cxu la
meza elemento egalas la valoro ni estas

23
00:01:15,040 --> 00:01:16,160
serĉi.

24
00:01:16,160 --> 00:01:21,030
Do se valoroj mezo egalas valoro, ni
povas reveni vera ekde ni trovis la

25
00:01:21,030 --> 00:01:22,810
valoron en nia tabelo.

26
00:01:22,810 --> 00:01:26,380
>> Sed se tio ne estis vera, nun
Ni bezonas fari la rekursiaj

27
00:01:26,380 --> 00:01:27,840
ŝtupo de duuma serĉo.

28
00:01:27,840 --> 00:01:30,450
Ni bezonas esplori ĉu al la
restis el la tabelo aŭ al la

29
00:01:30,450 --> 00:01:32,320
meze de la tabelo.

30
00:01:32,320 --> 00:01:39,280
Do jen, ni diru, se taksas je duono estas
malpli ol valoro, kiu signifas, ke valoro

31
00:01:39,280 --> 00:01:41,350
estis pli granda, ol la meza
de la tabelo.

32
00:01:41,350 --> 00:01:45,790
Do valoro devas esti al la rajto de la
elemento, ke ni nur rigardis.

33
00:01:45,790 --> 00:01:48,090
>> Do jen, ni iras al
serĉu rekursie.

34
00:01:48,090 --> 00:01:50,320
Kaj ni vidos rigardi kion ni pasante
al ĉi tio en sekundo.

35
00:01:50,320 --> 00:01:53,440
Sed ni tuj serĉi la
Dekstre de la meza elemento.

36
00:01:53,440 --> 00:01:57,710
Kaj en la alia kazo, tio signifas ke
valoro estis malpli ol la duono de la

37
00:01:57,710 --> 00:02:00,660
tabelo, kaj tial ni iras
sercxi maldekstren.

38
00:02:00,660 --> 00:02:03,520
Nun maldekstren tuj estos
iom pli facile rigardu.

39
00:02:03,520 --> 00:02:07,770
Do, ni vidas ĉi tie ke ni estas rekursie
nomante serĉo kie la unua

40
00:02:07,770 --> 00:02:10,120
argumento estas, denove, la valoro
Ni serĉas super.

41
00:02:10,120 --> 00:02:14,970
La dua argumento tuj estos la
tabelo, ke ni estis serĉanta super.

42
00:02:14,970 --> 00:02:17,090
Kaj la lasta elemento nun estas meza.

43
00:02:17,090 --> 00:02:21,650
Memoru la lastan parametron estas nia int
n, do tio estas la longo de nia tabelo.

44
00:02:21,650 --> 00:02:25,310
>> En la rekursia alvoko por esplori, ni estas
nun dirante, ke la longeco de la

45
00:02:25,310 --> 00:02:27,230
tabelo estas meza.

46
00:02:27,230 --> 00:02:32,900
Do, se nia tabelo estis de grandeco 20 kaj ni
esploris ĉe indeksa 10, ekde mezo estas

47
00:02:32,900 --> 00:02:36,930
20 dividite per 2, tio signifas ke ni estas
pasante 10 kiel la nova

48
00:02:36,930 --> 00:02:38,300
longeco de nia tabelo.

49
00:02:38,300 --> 00:02:41,910
Memoru, ke kiam vi havas tabelo
de longo 10, kiu signifas la valida

50
00:02:41,910 --> 00:02:45,450
elementoj estas en indeksoj 0 tra 9.

51
00:02:45,450 --> 00:02:50,120
Do tiu estas ekzakte kion ni volas
specifi nia ĝisdatigita tabelo - maldekstre

52
00:02:50,120 --> 00:02:53,010
tabelo el la meza elemento.

53
00:02:53,010 --> 00:02:55,710
>> Do, rigardante dekstren estas
iom pli malfacila.

54
00:02:55,710 --> 00:03:00,170
Nun unue, ni konsideru la longo
de la tabelo al la rajto de la

55
00:03:00,170 --> 00:03:01,240
meza elemento.

56
00:03:01,240 --> 00:03:08,390
Do, se nia tabelo estis de amplekso n, tiam la
nova tabelo estos de amplekso n minus

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

58
00:03:10,140 --> 00:03:12,530
Do, ni pensu pri n minus mezo.

59
00:03:12,530 --> 00:03:18,710
>> Denove, se la tabelo estis de amplekso 20 kaj
Ni dividu per 2 al preni la mezo,

60
00:03:18,710 --> 00:03:23,540
do la meza estas 10, tiam n minus mezo
tuj donas al ni 10, do 10

61
00:03:23,540 --> 00:03:25,330
elementojn al la rajto de mezo.

62
00:03:25,330 --> 00:03:27,780
Sed ni ankaŭ havas ĉi tiun minus
1, pro tio ni ne volas

63
00:03:27,780 --> 00:03:29,700
inkluzivas la mezo mem.

64
00:03:29,700 --> 00:03:34,190
Do n minus mezo minus 1 donas al ni la
totala nombro de elementoj al la dekstra

65
00:03:34,190 --> 00:03:36,800
el la mezo indekso en la tabelo.

66
00:03:36,800 --> 00:03:41,870
>> Nun ĉi tie, memoru, ke la meza
parametro estas la valoroj tabelo.

67
00:03:41,870 --> 00:03:46,180
Do jen, ni pasas al
ĝisdatigita valoroj tabelo.

68
00:03:46,180 --> 00:03:50,930
Ĉi valoroj plus duono plus 1 estas
reale dirante rekursie voki

69
00:03:50,930 --> 00:03:56,460
search, pasante en nova tabelo, kie
ke novaj tabelo startas en la mezo

70
00:03:56,460 --> 00:03:59,370
plus unu de niaj originalaj valoroj tabelo.

71
00:03:59,370 --> 00:04:05,400
>> Alternativa sintakso por tio, nun ke
vi jam komencis vidi montriloj, estas

72
00:04:05,400 --> 00:04:10,170
ampersand valoroj mezo plus 1.

73
00:04:10,170 --> 00:04:17,149
Do, kaptu la adreso de la mezo
plus unu elemento de valoroj.

74
00:04:17,149 --> 00:04:23,690
>> Nun, se vi ne estis komforta
modifi tabelon kiel ke, vi

75
00:04:23,690 --> 00:04:28,900
povus ankaux esti implementado ĉi uzante
rekursia helpanton funkcio, kie

76
00:04:28,900 --> 00:04:31,680
ke helpanto funkcio prenas
pli argumentojn.

77
00:04:31,680 --> 00:04:36,610
Do anstataŭ preni nur la valoro, la
tabelo, kaj la grandeco de la tabelo,

78
00:04:36,610 --> 00:04:42,315
helpanto funkcio povus preni pli
argumentoj, inkluzive de la suba indekso

79
00:04:42,315 --> 00:04:45,280
ke vi zorgas pri la tabelo
kaj la supra indico kiu vi zorgas

80
00:04:45,280 --> 00:04:46,300
pri la tabelo.

81
00:04:46,300 --> 00:04:49,770
>> Kaj tiel konservanta trako de ambaŭ la malsupra
indekso kaj la supra indico, vi ne

82
00:04:49,770 --> 00:04:52,780
bezonas iam modifi la
originalaj valoroj tabelo.

83
00:04:52,780 --> 00:04:56,390
Vi povas simple daŭre
uzi la valoroj tabelo.

84
00:04:56,390 --> 00:04:59,540
Sed ĉi tie, rimarki ke ni ne bezonas helpantojn
funkcii kiel longa kiel ni estas

85
00:04:59,540 --> 00:05:01,760
volante modifi la originalan
valorojn tabelo.

86
00:05:01,760 --> 00:05:05,020
Ni pretas Iam en
ĝisdatigita valoroj.

87
00:05:05,020 --> 00:05:09,140
>> Nun, ni ne povas duuma serĉo super
tabelo, kiu estas Unsorted.

88
00:05:09,140 --> 00:05:12,220
Do, ni ricevas tiun ordo ekstere.

89
00:05:12,220 --> 00:05:17,650
Nun, rimarki ke varo estas pasintaj du
parametroj int valoroj, kiuj estas la

90
00:05:17,650 --> 00:05:21,110
tabelo, ke ni ordig kaj int n,
kiu estas la longo de la tabelo, kiu

91
00:05:21,110 --> 00:05:22,250
ni ordig.

92
00:05:22,250 --> 00:05:24,840
Do, ĉi tie ni volas apliki
ordiga algoritmo

93
00:05:24,840 --> 00:05:26,690
ke estas o de n kvadratoj.

94
00:05:26,690 --> 00:05:30,560
Vi povus elekti bobelo varon, elekto
varon, aŭ inserción varon, aŭ

95
00:05:30,560 --> 00:05:32,670
iu alia speco ke ni havas ne
vidis en la klaso.

96
00:05:32,670 --> 00:05:36,380
Sed cxi tie, ni iras al
uzi selektado varo.

97
00:05:36,380 --> 00:05:40,030
>> Do, ni iras al persisti
super la tuta tabelo.

98
00:05:40,030 --> 00:05:44,360
Nu, jen ni vidas ke ni estas ripetanta
de 0 al n minus 1.

99
00:05:44,360 --> 00:05:45,990
Kial ne la tuta vojo ĝis n?

100
00:05:45,990 --> 00:05:49,320
Nu, se ni jam ordigitaj la unua
n minus 1 elementoj, tiam la

101
00:05:49,320 --> 00:05:54,420
lasta elemento kio devas jam esti
en la ĝusta loko, do ordig super

102
00:05:54,420 --> 00:05:56,520
en la tuta tabelo.

103
00:05:56,520 --> 00:05:58,770
>> Nu, memoru, kiamaniere selektado
speco funkcias.

104
00:05:58,770 --> 00:06:01,950
Ni tuj iras trans la tuta tabelo
serĉante la minimuma valoro en

105
00:06:01,950 --> 00:06:04,480
la tabelo kaj bastono ke
en la komenco.

106
00:06:04,480 --> 00:06:07,610
Tiam ni tuj iru super la tuta
tabelo denove serĉas la dua

107
00:06:07,610 --> 00:06:10,410
plej malgranda ero, kaj bastono ke
en la dua pozicio en la

108
00:06:10,410 --> 00:06:12,100
tabelo, kaj tiel plu.

109
00:06:12,100 --> 00:06:14,330
Do, tio estas kion tiu faras.

110
00:06:14,330 --> 00:06:17,290
>> Tie, ni vidas ke ni estas
opcio la aktuala minimuma

111
00:06:17,290 --> 00:06:20,030
valoro al la i-a indekso.

112
00:06:20,030 --> 00:06:23,160
Do en la unua ripeto, ni iras
konsideri la minimuman valoron por esti

113
00:06:23,160 --> 00:06:25,030
la komencon de nia tabelo.

114
00:06:25,030 --> 00:06:28,500
Poste, ni iras al persisti super la
restaĵon de la tabelo, kontrolanta al

115
00:06:28,500 --> 00:06:31,870
vidi se nenia elementoj pli malgrandaj ol
kiu ni aktuale

116
00:06:31,870 --> 00:06:33,900
konsiderante la minimumo.

117
00:06:33,900 --> 00:06:38,840
>> Do jen, valoroj j plus unu - tio estas
malpli ol kion ni estas aktuale

118
00:06:38,840 --> 00:06:40,380
konsiderante la minimumo.

119
00:06:40,380 --> 00:06:42,940
Tiam ni iras por ĝisdatigi kio
Ni pensas estas la minimumo por

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

121
00:06:44,640 --> 00:06:48,540
Do, faru, ke tra la tuta tabelo,
kaj post tio por buklo, minimuma

122
00:06:48,540 --> 00:06:53,160
devus esti la minimuma ero de
la i-a pozicio en la tabelo.

123
00:06:53,160 --> 00:06:57,350
>> Iam ni havas tion, ni povas interŝanĝi la
minimuma valoro en la i-a pozicio

124
00:06:57,350 --> 00:06:58,230
en la tabelo.

125
00:06:58,230 --> 00:07:00,130
Do tiu estas nur normo swap.

126
00:07:00,130 --> 00:07:03,940
Ni stokas en portempa valoro -
la i-a valoro en la tabelo -

127
00:07:03,940 --> 00:07:08,460
meti en la i-a valoro en la tabelo la
minimuma valoro kiu apartenas tie,

128
00:07:08,460 --> 00:07:13,580
kaj do gardi reen en kie la
aktuala minimuma valoro kutimis esti la

129
00:07:13,580 --> 00:07:16,460
i-a valoro en la tabelo, do
ke ni ne perdos.

130
00:07:16,460 --> 00:07:20,510
>> Do, kiu daŭrigas en
la sekva ripeto.

131
00:07:20,510 --> 00:07:23,480
Ni komencos serĉi la duan
minimuma valoro kaj enmeti tion en la

132
00:07:23,480 --> 00:07:24,590
dua pozicio.

133
00:07:24,590 --> 00:07:27,440
Sur la tria ripeta, ni devos serĉi
la tria minimuma valoro kaj insert

134
00:07:27,440 --> 00:07:31,550
ke en la tria pozicio, kaj tial
plu ĝis ni havos ordo tabelo.

135
00:07:31,550 --> 00:07:33,820
Mia nomo estas Rob, kaj ĉi
Estis elekto varo.

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