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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Hi, jien Rob.

3
00:00:15,010 --> 00:00:16,790
Kif aħna jimpjegaw tfittxija binarja?

4
00:00:16,790 --> 00:00:18,770
Ejja nsib.

5
00:00:18,770 --> 00:00:23,400
Allura, innota li dan tfittxija aħna qed tmur
biex jimplimentaw recursively.

6
00:00:23,400 --> 00:00:27,470
Inti tista 'wkoll timplimenta tfittxija binarja
iteratively, hekk jekk inti ma dan,

7
00:00:27,470 --> 00:00:29,280
li perfettament multa.

8
00:00:29,280 --> 00:00:32,820
>> Issa l-ewwel, ejja niftakru dak l-
parametri ta 'tiftix huma intenzjonati li jkunu.

9
00:00:32,820 --> 00:00:36,120
Hawnhekk, naraw valur int, li hija
suppost ikunu l-valur l-utent huwa

10
00:00:36,120 --> 00:00:37,320
tiftix għal.

11
00:00:37,320 --> 00:00:40,800
Naraw l-array valuri int, li
hija l-array li aħna qed

12
00:00:40,800 --> 00:00:42,520
tiftix għall-valur.

13
00:00:42,520 --> 00:00:45,602
U naraw int n, li hija
it-tul ta 'firxa tagħna.

14
00:00:45,602 --> 00:00:47,410
>> Issa, l-ewwel ħaġa l-ewwel.

15
00:00:47,410 --> 00:00:51,350
Aħna tikkontrolla biex tara jekk n ikun egwali għal 0, b'mod
f'liema każ nerġgħu lura falza.

16
00:00:51,350 --> 00:00:54,770
Li jinsab biss qal jekk għandna vojt
firxa, il-valur huwa b'mod ċar mhux fi

17
00:00:54,770 --> 00:00:57,860
array vojta, sabiex inkunu nistgħu ritorn foloz.

18
00:00:57,860 --> 00:01:01,250
>> Issa, aħna fil-fatt tixtieq li tagħmel il-binarju
parti tfittxija tat-tfittxija binarja.

19
00:01:01,250 --> 00:01:04,780
Għalhekk, irridu isibu l-nofs
element ta 'din array.

20
00:01:04,780 --> 00:01:09,130
Hawnhekk, irridu ngħidu nofs ugwali n maqsuma
bi 2, peress li l-element tan-nofs huwa

21
00:01:09,130 --> 00:01:12,240
se jkun it-tul ta '
firxa tagħna diviż bil 2.

22
00:01:12,240 --> 00:01:15,040
Issa aħna qed tmur biex tikkontrolla biex tara jekk l-
element nofs huwa ugwali għall-valur nkunu

23
00:01:15,040 --> 00:01:16,160
tiftix għal.

24
00:01:16,160 --> 00:01:21,030
Mela jekk valuri nofs ugwali valur, aħna
jistgħu jirritornaw veru peress li sibna l-

25
00:01:21,030 --> 00:01:22,810
valur fil-firxa tagħna.

26
00:01:22,810 --> 00:01:26,380
>> Imma jekk dan ma kienx veru, issa
għandna bżonn biex jagħmlu l-rikursivi

27
00:01:26,380 --> 00:01:27,840
pass ta 'tfittxija binarja.

28
00:01:27,840 --> 00:01:30,450
Għandna bżonn li tfittex jew lill-
xellug tal-firxa jew l-

29
00:01:30,450 --> 00:01:32,320
nofs tal-firxa.

30
00:01:32,320 --> 00:01:39,280
So here, ngħidu jekk il-valuri fil-nofs huwa
inqas mill-valur, dan ifisser li l-valur

31
00:01:39,280 --> 00:01:41,350
kienet akbar minn-nofs
tal-firxa.

32
00:01:41,350 --> 00:01:45,790
Allura valur għandu jkun li d-dritt tal-
element li aħna biss ħares lejn.

33
00:01:45,790 --> 00:01:48,090
>> Allura hawn, aħna qed tmur biex
tfittxija recursively.

34
00:01:48,090 --> 00:01:50,320
U aħna ser tħares lejn dak li aħna qed tgħaddi
għal dan fit-tieni.

35
00:01:50,320 --> 00:01:53,440
Iżda aħna qed tmur biex tfittex għall-
lemin tal-element tan-nofs.

36
00:01:53,440 --> 00:01:57,710
U fil-każ ieħor, dan ifisser li
valur kien inqas minn-nofs tal-

37
00:01:57,710 --> 00:02:00,660
array, u hekk aħna qed tmur
biex tfittex lejn ix-xellug.

38
00:02:00,660 --> 00:02:03,520
Issa, ix-xellug se tkun
daqsxejn aktar faċli li tħares lejn.

39
00:02:03,520 --> 00:02:07,770
Allura, naraw li aħna hawnhekk qed recursively
ssejjaħ tfittxija fejn l-ewwel

40
00:02:07,770 --> 00:02:10,120
argument huwa, għal darb'oħra, il-valur
aħna qed tfittex fuq.

41
00:02:10,120 --> 00:02:14,970
It-tieni argument se tkun l-
array li konna tiftix fuq.

42
00:02:14,970 --> 00:02:17,090
U l-aħħar element huwa issa nofs.

43
00:02:17,090 --> 00:02:21,650
Ftakar l-aħħar parametru huwa int tagħna
n, b'tali mod li t-tul ta 'firxa tagħna.

44
00:02:21,650 --> 00:02:25,310
>> Fis-sejħa rikursivi li persuna tfittex, aħna qed
issa tgħid li t-tul tal-

45
00:02:25,310 --> 00:02:27,230
firxa hija nofs.

46
00:02:27,230 --> 00:02:32,900
Għalhekk, jekk firxa tagħna kienet ta 'daqs 20 u aħna
mfittxija fil-indiċi 10, peress tan-nofs huwa

47
00:02:32,900 --> 00:02:36,930
20 diviż bi 2, dan ifisser li aħna qed
tgħaddi 10 bħala l-ġdid

48
00:02:36,930 --> 00:02:38,300
tul ta 'firxa tagħna.

49
00:02:38,300 --> 00:02:41,910
Ftakar li meta inti għandek firxa
ta 'tul ta' 10, dan ifisser l valida

50
00:02:41,910 --> 00:02:45,450
elementi huma indiċi 0 sa 9.

51
00:02:45,450 --> 00:02:50,120
Allura dan huwa eżattament dak li rridu
tispeċifika firxa aġġornata tagħna - fuq ix-xellug

52
00:02:50,120 --> 00:02:53,010
array mill-element nofs.

53
00:02:53,010 --> 00:02:55,710
>> Għalhekk, tħares lejn il-lemin hija
daqsxejn aktar diffiċli.

54
00:02:55,710 --> 00:03:00,170
Issa l-ewwel, ejja jikkunsidraw it-tul
ta 'l-array għad-dritt ta' l-

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

56
00:03:01,240 --> 00:03:08,390
Għalhekk, jekk firxa tagħna kienet ta 'daqs n, allura l-
firxa ġdida se tkun ta 'minus daqs n

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

58
00:03:10,140 --> 00:03:12,530
Allura, ejja jaħsbu n-nofs minus.

59
00:03:12,530 --> 00:03:18,710
>> Għal darb'oħra, jekk il-firxa kienu ta 'daqs 20 u
aħna iddividi 2 li jiksbu l-tan-nofs,

60
00:03:18,710 --> 00:03:23,540
hekk-nofs huwa ta '10, allura n nieqes nofs
se tagħtina 10, hekk 10

61
00:03:23,540 --> 00:03:25,330
elementi għad-dritt ta 'nofs.

62
00:03:25,330 --> 00:03:27,780
Iżda għandna wkoll dan minus
1, peress li aħna ma rridux li

63
00:03:27,780 --> 00:03:29,700
jinkludu l-nofs innifsu.

64
00:03:29,700 --> 00:03:34,190
Allura n minus nofs minus 1 jagħtina l-
numru totali ta 'elementi lejn il-lemin

65
00:03:34,190 --> 00:03:36,800
ta 'l-indiċi tan-nofs fil-firxa.

66
00:03:36,800 --> 00:03:41,870
>> Issa hawnhekk, ftakar li l-nofs
parametru huwa l-array valuri.

67
00:03:41,870 --> 00:03:46,180
Allura hawn, aħna qed jgħaddu minn
aġġornata valuri array.

68
00:03:46,180 --> 00:03:50,930
Dan valuri plus plus nofs 1 tkun
attwalment qal recursively sejħa

69
00:03:50,930 --> 00:03:56,460
tfittxija, li jgħaddi fil-firxa ġdida, fejn
li array ġdid jibda fin-nofs

70
00:03:56,460 --> 00:03:59,370
plus wieħed mill-valuri oriġinali firxa tagħna.

71
00:03:59,370 --> 00:04:05,400
>> Sintassi sostitut għal dan, issa li
inti stajt beda biex tara pointers, huwa

72
00:04:05,400 --> 00:04:10,170
Valuri ampersand plus nofs 1.

73
00:04:10,170 --> 00:04:17,149
Allura, grab-indirizz tat-nofs
plus element wieħed tal-valuri.

74
00:04:17,149 --> 00:04:23,690
>> Issa, jekk inti ma kinux komdi
timmodifika firxa bħal dik, inti

75
00:04:23,690 --> 00:04:28,900
tista 'wkoll implimentaw dan bl-użu
funzjoni helper jirrikorri, fejn

76
00:04:28,900 --> 00:04:31,680
dik il-funzjoni helper jieħu
aktar argumenti.

77
00:04:31,680 --> 00:04:36,610
Allura minflok tieħu biss il-valur, l-
array, u d-daqs tal-array,

78
00:04:36,610 --> 00:04:42,315
il-funzjoni helper tista 'tieħu aktar
argumenti, inkluż l-indiċi t'isfel

79
00:04:42,315 --> 00:04:45,280
li inti jimpurtak fil-firxa
u l-indiċi ta 'fuq li inti kura

80
00:04:45,280 --> 00:04:46,300
dwar il-firxa.

81
00:04:46,300 --> 00:04:49,770
>> U hekk iżżomm rekord ta 'kemm l-aktar baxx
indiċi u l-indiċi ta 'fuq, inti ma

82
00:04:49,770 --> 00:04:52,780
jeħtieġ li qatt timmodifika l-
valuri oriġinali array.

83
00:04:52,780 --> 00:04:56,390
Tista 'biss tibqa'
jużaw il-firxa valuri.

84
00:04:56,390 --> 00:04:59,540
Iżda hawnhekk, avviż li ma kellniex bżonn helper
jiffunzjonaw sakemm aħna qed

85
00:04:59,540 --> 00:05:01,760
lesti li timmodifika l-oriġinali
valuri array.

86
00:05:01,760 --> 00:05:05,020
Aħna lesti li jgħaddu
AN valuri aġġornati.

87
00:05:05,020 --> 00:05:09,140
>> Issa, ma nistgħux tfittxija binarja fuq
firxa li mhux magħżul.

88
00:05:09,140 --> 00:05:12,220
Allura, ejja nikseb dan mifthiema.

89
00:05:12,220 --> 00:05:17,650
Issa, avviż li sort huwa żewġ passat
parametri int valuri, li hija l-

90
00:05:17,650 --> 00:05:21,110
array li aħna qed issortjar, u int n,
li huwa t-tul tal-firxa li

91
00:05:21,110 --> 00:05:22,250
aħna qed issortjar.

92
00:05:22,250 --> 00:05:24,840
Allura, hawn irridu li jimplimentaw
algoritmu issortjar

93
00:05:24,840 --> 00:05:26,690
dan huwa o ta n kwadru.

94
00:05:26,690 --> 00:05:30,560
Inti tista 'tagħżel it-tip bubble, l-għażla
sort, jew sort inserzjoni, jew

95
00:05:30,560 --> 00:05:32,670
xi tip ieħor aħna ma
jidhru fil-klassi.

96
00:05:32,670 --> 00:05:36,380
Iżda hawnhekk, aħna qed tmur biex
jużaw sort għażla.

97
00:05:36,380 --> 00:05:40,030
>> Allura, aħna qed tmur biex jtenni
fuq il-firxa sħiħa.

98
00:05:40,030 --> 00:05:44,360
Well, hawn naraw li aħna qed mtennija
minn 0 sa n minus 1.

99
00:05:44,360 --> 00:05:45,990
Għaliex ma-triq kollha sa n?

100
00:05:45,990 --> 00:05:49,320
Ukoll, jekk aħna stajt diġà magħżula l-ewwel
n nieqes 1 elementi, allura l-

101
00:05:49,320 --> 00:05:54,420
ħafna aħħar element dak li għandu jkun diġà
fil-post korrett, hekk issortjar fuq

102
00:05:54,420 --> 00:05:56,520
l-array kollu.

103
00:05:56,520 --> 00:05:58,770
>> Issa, tiftakar kif selezzjoni
sort xogħlijiet.

104
00:05:58,770 --> 00:06:01,950
Aħna qed tmur biex jmorru fuq il-firxa sħiħa
tfittex l-valur minimu fil-

105
00:06:01,950 --> 00:06:04,480
il-firxa u stick li
fil-bidu.

106
00:06:04,480 --> 00:06:07,610
Allura aħna qed tmur biex jmorru fuq il-kollu
firxa darb'oħra tfittex għat-tieni

107
00:06:07,610 --> 00:06:10,410
element iżgħar, u stick li
fit-tieni pożizzjoni fil-

108
00:06:10,410 --> 00:06:12,100
firxa, u l-bqija.

109
00:06:12,100 --> 00:06:14,330
Allura, dak hu li dan qed tagħmel.

110
00:06:14,330 --> 00:06:17,290
>> Hawnhekk, aħna qed jaraw li aħna qed
iffissar tal-minimu attwali

111
00:06:17,290 --> 00:06:20,030
valur għall-indiċi i-th.

112
00:06:20,030 --> 00:06:23,160
Allura fuq l-ewwel iterazzjoni, aħna qed tmur
li tikkunsidra l-valur minimu li jkun

113
00:06:23,160 --> 00:06:25,030
il-bidu ta 'firxa tagħna.

114
00:06:25,030 --> 00:06:28,500
Imbagħad, aħna qed tmur biex jtenni fuq il-
bqija tal-firxa, il-verifika biex

115
00:06:28,500 --> 00:06:31,870
ara jekk hemm xi elementi iżgħar minn
il-wieħed li aħna qed bħalissa

116
00:06:31,870 --> 00:06:33,900
jikkunsidraw il-minimu.

117
00:06:33,900 --> 00:06:38,840
>> So here, valuri j plus wieħed - li
inqas minn dak li aħna bħalissa

118
00:06:38,840 --> 00:06:40,380
jikkunsidraw il-minimu.

119
00:06:40,380 --> 00:06:42,940
Imbagħad aħna qed tmur biex taġġorna dak
aħna naħsbu li hija l-minimu li

120
00:06:42,940 --> 00:06:44,640
indiċi j plus 1.

121
00:06:44,640 --> 00:06:48,540
Allura, jagħmlu dan madwar l-firxa sħiħa,
u wara dan għal loop, minimu

122
00:06:48,540 --> 00:06:53,160
għandu jkun l-element minima minn
il-pożizzjoni i-th fil-firxa.

123
00:06:53,160 --> 00:06:57,350
>> Ladarba għandna dan, nistgħu tpartit l-
valur minimu fil-pożizzjoni i-th

124
00:06:57,350 --> 00:06:58,230
fil-firxa.

125
00:06:58,230 --> 00:07:00,130
Allura din hija biss tpartit standard.

126
00:07:00,130 --> 00:07:03,940
Aħna jaħżen fil-valur temporanju -
il-valur i-th fil-firxa -

127
00:07:03,940 --> 00:07:08,460
tqiegħed fil-valur i-th fil-firxa tal-
valur minimu li jappartjeni hemmhekk,

128
00:07:08,460 --> 00:07:13,580
u mbagħad aħżen lura fil fejn il-
valur minimu kurrenti użati biex ikunu l-

129
00:07:13,580 --> 00:07:16,460
Valur i-th fil-array, hekk
li aħna ma titilfu.

130
00:07:16,460 --> 00:07:20,510
>> Allura, li tkompli fuq
l-iterazzjoni li jmiss.

131
00:07:20,510 --> 00:07:23,480
Aħna ser tibda tfittex għall-tieni
valur minimu u daħħal li fil-

132
00:07:23,480 --> 00:07:24,590
tieni pożizzjoni.

133
00:07:24,590 --> 00:07:27,440
Fit-tielet iterazzjoni, aħna ser tfittex
it-tielet valur minimu u daħħal

134
00:07:27,440 --> 00:07:31,550
li fit-tielet pożizzjoni, u għalhekk
fuq sakemm għandna firxa Issortjati.

135
00:07:31,550 --> 00:07:33,820
Jisimni Rob, u dan
kien sort għażla.

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