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

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

3
00:00:15,010 --> 00:00:16,790
Paano nagpapatupad kami ng isang binary paghahanap?

4
00:00:16,790 --> 00:00:18,770
Ng malaman Hayaan.

5
00:00:18,770 --> 00:00:23,400
Kaya, tandaan na ang paghahanap na ito kami ay pagpunta
ipatupad recursively.

6
00:00:23,400 --> 00:00:27,470
Maaari mo ring ipatupad ang binary paghahanap
iteratively, kaya kung ginawa mo iyon,

7
00:00:27,470 --> 00:00:29,280
na perpektong fine.

8
00:00:29,280 --> 00:00:32,820
>> Unang Ngayon, ni tandaan ipaalam kung ano ang
mga parameter sa paghahanap ay nilalayong maging.

9
00:00:32,820 --> 00:00:36,120
Dito, makikita natin halaga int, na
dapat na maging ang halaga gumagamit ay

10
00:00:36,120 --> 00:00:37,320
naghahanap para sa.

11
00:00:37,320 --> 00:00:40,800
Nakakakita kami ng mga halaga int array, na
ay ang array na kung saan kami ay

12
00:00:40,800 --> 00:00:42,520
naghahanap ng mga halaga.

13
00:00:42,520 --> 00:00:45,602
At nakita namin int n, na
ang haba ng aming array.

14
00:00:45,602 --> 00:00:47,410
>> Ngayon, ang unang bagay na unang.

15
00:00:47,410 --> 00:00:51,350
Nagsusuri kami upang makita kung n ay katumbas ng 0, sa
kung saan bumalik kami ng hindi totoo.

16
00:00:51,350 --> 00:00:54,770
Na lang sinasabi kung kami ay may isang walang laman
array, halaga ay malinaw na hindi sa isang

17
00:00:54,770 --> 00:00:57,860
Walang laman ang array, upang maaari naming ibalik hindi totoo.

18
00:00:57,860 --> 00:01:01,250
>> Ngayon, gusto talaga naming gawin ang binary
bahagi ng paghahanap ng binary paghahanap.

19
00:01:01,250 --> 00:01:04,780
Kaya, nais naming hanapin ang gitna
elemento ng array.

20
00:01:04,780 --> 00:01:09,130
Dito, sinasabi namin gitna katumbas n hinati
sa pamamagitan ng 2, dahil sa gitna elemento ay

21
00:01:09,130 --> 00:01:12,240
pagpunta sa maging ang haba ng
ang aming array na hinati sa 2.

22
00:01:12,240 --> 00:01:15,040
Ngayon kami ay pagpunta sa suriin upang makita kung ang
gitnang elemento ay katumbas ng halaga Ikinalulungkot namin

23
00:01:15,040 --> 00:01:16,160
naghahanap para sa.

24
00:01:16,160 --> 00:01:21,030
Kaya kung halaga gitna ay katumbas ng halaga, namin
Maaari nagbabalik ng tunay na dahil nakita namin ang

25
00:01:21,030 --> 00:01:22,810
halaga sa aming array.

26
00:01:22,810 --> 00:01:26,380
>> Ngunit kung iyon ay hindi totoo, ngayon
kailangan namin upang gawin ang recursive

27
00:01:26,380 --> 00:01:27,840
hakbang ng binary paghahanap.

28
00:01:27,840 --> 00:01:30,450
Kailangan namin upang maghanap alinman sa
iniwan ng array o sa

29
00:01:30,450 --> 00:01:32,320
gitna ng array.

30
00:01:32,320 --> 00:01:39,280
Kaya dito, sinasabi namin kung halaga sa gitna ay
mas mababa sa halaga, na nangangahulugan na halaga

31
00:01:39,280 --> 00:01:41,350
ay mas mataas kaysa sa gitna
ng array.

32
00:01:41,350 --> 00:01:45,790
Kaya dapat sa kanan ng ang halaga
elemento na tumingin lang namin sa.

33
00:01:45,790 --> 00:01:48,090
>> Kaya dito, kami ay pagpunta sa
maghanap recursively.

34
00:01:48,090 --> 00:01:50,320
At titingnan namin kung ano kami ay pagpasa
upang ito sa isang segundo.

35
00:01:50,320 --> 00:01:53,440
Ngunit kami ay pagpunta upang maghanap sa
kanan ng gitna ng elemento.

36
00:01:53,440 --> 00:01:57,710
At sa iba pang mga kaso, ay nangangahulugan na na
halaga ay mas mababa kaysa sa gitna ng

37
00:01:57,710 --> 00:02:00,660
array, at sa gayon kami ay pagpunta
upang maghanap sa kaliwa.

38
00:02:00,660 --> 00:02:03,520
Ngayon, sa kaliwa ay magiging
medyo mas madali upang tumingin sa.

39
00:02:03,520 --> 00:02:07,770
Kaya, makikita natin dito na hindi namin recursively
pagtawag kung saan ang unang paghahanap

40
00:02:07,770 --> 00:02:10,120
argumento ay, muli, ang halaga
naghahanap kami ng mahigit.

41
00:02:10,120 --> 00:02:14,970
Ang pangalawang argumento ay magiging ang
array na tayo ay naghahanap sa ibabaw.

42
00:02:14,970 --> 00:02:17,090
At ang huling elemento ang gitnang ngayon.

43
00:02:17,090 --> 00:02:21,650
Tandaan ang huling parameter ay ang aming int
n, kaya iyon ang haba ng aming array.

44
00:02:21,650 --> 00:02:25,310
>> Sa recursive tawag upang maghanap, hindi namin
ngayon na nagsasabi na ang haba ng

45
00:02:25,310 --> 00:02:27,230
array ay gitna.

46
00:02:27,230 --> 00:02:32,900
Kaya, kung ang aming array ay ng laki 20 at kami
Naghanap sa index 10, dahil gitna ay

47
00:02:32,900 --> 00:02:36,930
20 na hinati sa 2, na nangangahulugan na namin
pagpasa sa 10 bilang bagong

48
00:02:36,930 --> 00:02:38,300
haba ng aming array.

49
00:02:38,300 --> 00:02:41,910
Tandaan na kapag mayroon kang isang array
ng haba 10, ay nangangahulugan na ang wastong

50
00:02:41,910 --> 00:02:45,450
mga elemento ay nasa mga indeks ng 0 hanggang 9.

51
00:02:45,450 --> 00:02:50,120
Kaya ito ay kung ano mismo ang gusto naming
tukuyin ang aming na-update array - kaliwa

52
00:02:50,120 --> 00:02:53,010
array mula sa gitna ng elemento.

53
00:02:53,010 --> 00:02:55,710
>> Kaya, naghahanap sa kanan ay
medyo mas mahirap.

54
00:02:55,710 --> 00:03:00,170
Unang Ngayon, isaalang-alang na ang haba ipaalam
ng array sa kanan ng

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

56
00:03:01,240 --> 00:03:08,390
Kaya, kung ang aming array ay ng laki n, pagkatapos ay ang
bagong array ay magiging ng laki n minus

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

58
00:03:10,140 --> 00:03:12,530
Kaya, sa tingin ng n minus gitna ipaalam.

59
00:03:12,530 --> 00:03:18,710
>> Muli, kung ang array ay ng laki 20 at
hinati namin sa pamamagitan ng 2 upang makuha ang gitna,

60
00:03:18,710 --> 00:03:23,540
kaya sa gitna ay 10, pagkatapos n minus gitna
ay pagpunta sa bigyan kami ng 10, kaya 10

61
00:03:23,540 --> 00:03:25,330
mga elemento sa kanan ng gitna.

62
00:03:25,330 --> 00:03:27,780
Ngunit mayroon din namin ito minus
1, dahil hindi namin nais na

63
00:03:27,780 --> 00:03:29,700
Kasama sa gitna mismo.

64
00:03:29,700 --> 00:03:34,190
Kaya n minus gitna minus 1 ay nagbibigay sa amin ang
kabuuang bilang ng mga elemento sa kanan

65
00:03:34,190 --> 00:03:36,800
ng gitna index sa array.

66
00:03:36,800 --> 00:03:41,870
>> Ngayon dito, tandaan na ang gitna
parameter ay ang mga halaga ng array.

67
00:03:41,870 --> 00:03:46,180
Kaya dito, naka-pagpasa kami ng isang
na-update na mga halaga ng array.

68
00:03:46,180 --> 00:03:50,930
Ang mga halaga plus gitna plus 1 ay
talagang sinasabi recursively tumawag

69
00:03:50,930 --> 00:03:56,460
paghahanap, ang pagpasa sa isang bagong array, kung saan
na ang mga bagong array ay nagsisimula sa gitna

70
00:03:56,460 --> 00:03:59,370
plus isa sa aming mga orihinal na halaga ng array.

71
00:03:59,370 --> 00:04:05,400
>> Isang kahaliling syntax para sa na, ngayon na
sinimulan mo upang makita ang mga payo, ay

72
00:04:05,400 --> 00:04:10,170
mga halaga ng ampersand gitna plus 1.

73
00:04:10,170 --> 00:04:17,149
Kaya, grab ng address ng gitnang
plus ang isang elemento ng mga halaga.

74
00:04:17,149 --> 00:04:23,690
>> Ngayon, kung ikaw ay hindi komportable
pagbabago ng isang array tulad ng na, ikaw

75
00:04:23,690 --> 00:04:28,900
maaari ring nagpatupad ito gamit
isang recursive function na lingkod, kung saan

76
00:04:28,900 --> 00:04:31,680
na lingkod function na tumatagal
higit pang mga argumento.

77
00:04:31,680 --> 00:04:36,610
Kaya sa halip ng pagkuha lamang ang halaga, ang
array, at sa laki ng array,

78
00:04:36,610 --> 00:04:42,315
ang lingkod ng function ay maaaring tumagal nang higit pa
mga argument, kabilang ang mas mababang index

79
00:04:42,315 --> 00:04:45,280
na nais mong mag-intindi sa array
at ang itaas na index na mahalaga sa iyo

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

81
00:04:46,300 --> 00:04:49,770
>> At kaya pagpapanatiling track ng parehong mga mas mababang
index at itaas na index, hindi mo gusto

82
00:04:49,770 --> 00:04:52,780
kailangan upang kailanman baguhin ang
orihinal na halaga ng array.

83
00:04:52,780 --> 00:04:56,390
Maaari mo lamang patuloy na
gamitin ang mga halaga ng array.

84
00:04:56,390 --> 00:04:59,540
Ngunit dito, mapapansin hindi namin kailangan ang isang lingkod
aandar hanggat hindi namin

85
00:04:59,540 --> 00:05:01,760
payag upang baguhin ang orihinal
mga halaga ng array.

86
00:05:01,760 --> 00:05:05,020
Kami ay handa upang pumasa sa
isang na-update na mga halaga.

87
00:05:05,020 --> 00:05:09,140
>> Ngayon, hindi namin maaari binary paghahanap sa paglipas ng
isang array na ay unsorted.

88
00:05:09,140 --> 00:05:12,220
Kaya, sabihin makakuha ng ito pinagsunod-sunod out.

89
00:05:12,220 --> 00:05:17,650
Ngayon, mapapansin na ang uri ay nakalipas na dalawang
mga parameter int value, kung saan ay ang

90
00:05:17,650 --> 00:05:21,110
array na aming pag-uuri, at int n,
kung saan ay ang haba ng array na

91
00:05:21,110 --> 00:05:22,250
kami ay pag-uuri.

92
00:05:22,250 --> 00:05:24,840
Kaya, dito gusto naming ipatupad
isang pag-uuri algorithm

93
00:05:24,840 --> 00:05:26,690
na o ng n nakalapat.

94
00:05:26,690 --> 00:05:30,560
Maaari kang pumili ng bubble sort, seleksyon
-uri-uriin, o uri pagpapasok, o

95
00:05:30,560 --> 00:05:32,670
ilang iba pang mga uri mayroon kaming hindi
nakikita sa klase.

96
00:05:32,670 --> 00:05:36,380
Ngunit dito, kami ay pagpunta sa
gamitin uriin pagpili.

97
00:05:36,380 --> 00:05:40,030
>> Kaya, kami ay pagpunta upang umulit
sa ibabaw ng buong array.

98
00:05:40,030 --> 00:05:44,360
Well, dito makita namin na kami ay iterating
mula 0 hanggang n minus 1.

99
00:05:44,360 --> 00:05:45,990
Bakit hindi lahat ng mga paraan ng hanggang sa n?

100
00:05:45,990 --> 00:05:49,320
Well, kung na pinagsunod-sunod na namin ang unang
n minus 1 elemento, pagkatapos ay ang

101
00:05:49,320 --> 00:05:54,420
napaka huling elemento kung ano ang dapat na maging
sa tamang lugar, kaya pag-uuri sa ibabaw

102
00:05:54,420 --> 00:05:56,520
ang buong array.

103
00:05:56,520 --> 00:05:58,770
>> Ngayon, tandaan kung paano seleksyon
uri gumagana.

104
00:05:58,770 --> 00:06:01,950
Kami ay pagpunta sa pumunta sa buong array
naghahanap para sa minimum na halaga sa

105
00:06:01,950 --> 00:06:04,480
ang array at stick na
sa simula.

106
00:06:04,480 --> 00:06:07,610
Pagkatapos kami ay pagpunta sa pumunta sa ibabaw ng buong
array muli naghahanap para sa ikalawang

107
00:06:07,610 --> 00:06:10,410
pinakamaliliit na elemento, at stick na
sa pangalawang posisyon sa

108
00:06:10,410 --> 00:06:12,100
array, at iba pa.

109
00:06:12,100 --> 00:06:14,330
Kaya, na kung ano ito ay ginagawa.

110
00:06:14,330 --> 00:06:17,290
>> Dito, kami ay nakakakita na kami
pag-set ang kasalukuyang minimum na

111
00:06:17,290 --> 00:06:20,030
ng halaga sa i-ika-index.

112
00:06:20,030 --> 00:06:23,160
Kaya sa unang iteration, kami ay pagpunta
upang isaalang-alang ang minimum na halaga na maging

113
00:06:23,160 --> 00:06:25,030
simula ng aming array.

114
00:06:25,030 --> 00:06:28,500
Pagkatapos, kami ay pagpunta upang umulit sa ibabaw ng
natitira sa array, pagsuri sa

115
00:06:28,500 --> 00:06:31,870
makita kung mayroong anumang mga elemento na mas maliit sa
ang isa na hindi namin kasalukuyan

116
00:06:31,870 --> 00:06:33,900
kung isasaalang-alang ang minimum.

117
00:06:33,900 --> 00:06:38,840
>> Kaya dito, mga halaga, values ​​j plus isa - iyon
mas mababa kaysa sa kung ano tayo sa kasalukuyan

118
00:06:38,840 --> 00:06:40,380
kung isasaalang-alang ang minimum.

119
00:06:40,380 --> 00:06:42,940
Pagkatapos kami ay pagpunta sa i-update ang ano
sa tingin namin ay ang minimum na

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

121
00:06:44,640 --> 00:06:48,540
Kaya, gawin iyon sa buong array,
at pagkatapos na ito para sa loop, minimum

122
00:06:48,540 --> 00:06:53,160
ay dapat na ang minimum na elemento mula sa
ang posisyon i-ika sa array.

123
00:06:53,160 --> 00:06:57,350
>> Sa sandaling mayroon kaming na, maaari naming magpalit ang
minimum na halaga sa i-ika-posisyon

124
00:06:57,350 --> 00:06:58,230
sa array.

125
00:06:58,230 --> 00:07:00,130
Kaya ito ay lamang ng isang standard na swap.

126
00:07:00,130 --> 00:07:03,940
Nag-iimbak kami sa isang pansamantalang halaga -
ang halaga i-ika sa array -

127
00:07:03,940 --> 00:07:08,460
Nailagay ang halaga i-ika sa array ang
minimum na halaga na pag-aari doon,

128
00:07:08,460 --> 00:07:13,580
at pagkatapos ay mag-imbak pabalik sa kung saan ang
kasalukuyang minimum na halaga na ginamit upang maging ang

129
00:07:13,580 --> 00:07:16,460
ika-i halaga sa array, kaya
na hindi namin ginawa mawala ito.

130
00:07:16,460 --> 00:07:20,510
>> Kaya, na patuloy sa
sa susunod na pag-ulit.

131
00:07:20,510 --> 00:07:23,480
Sisimulan naming naghahanap para sa ikalawang
minimum na halaga at ipasok iyon sa

132
00:07:23,480 --> 00:07:24,590
pangalawang posisyon.

133
00:07:24,590 --> 00:07:27,440
Sa ikatlong-ulit, titingnan namin para sa
ang ikatlong minimum na halaga at insert

134
00:07:27,440 --> 00:07:31,550
na papunta sa pangatlong posisyon, at iba pa
sa hanggang mayroon kaming pinagsunod-sunod ng array.

135
00:07:31,550 --> 00:07:33,820
Ang pangalan ko ay Rob, at ito
ay uri pagpili.

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