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

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

3
00:00:15,010 --> 00:00:16,790
Hoe kan ons in diens 'n binêre soek?

4
00:00:16,790 --> 00:00:18,770
Kom ons vind uit.

5
00:00:18,770 --> 00:00:23,400
So, daarop te let dat dit soek gaan ons
rekursief implementeer.

6
00:00:23,400 --> 00:00:27,470
Jy kan ook implementeer binêre soek
iteratief, so as jy dit gedoen het,

7
00:00:27,470 --> 00:00:29,280
dit is heeltemal fyn.

8
00:00:29,280 --> 00:00:32,820
>> Nou eers, laat ons onthou wat die
parameters te soek, is bedoel om te wees.

9
00:00:32,820 --> 00:00:36,120
Hier sien ons int waarde, wat
veronderstel om die waarde van die gebruiker is om te wees

10
00:00:36,120 --> 00:00:37,320
soek.

11
00:00:37,320 --> 00:00:40,800
Ons sien die int waardes skikking, wat
is die skikking in wat ons is

12
00:00:40,800 --> 00:00:42,520
soek na waarde.

13
00:00:42,520 --> 00:00:45,602
En ons sien int n, wat
Die lengte van ons verskeidenheid.

14
00:00:45,602 --> 00:00:47,410
>> Nou, in die eerste ding wat eerste.

15
00:00:47,410 --> 00:00:51,350
Ons gaan om te sien of n gelyk aan 0, in
welke geval ons terugkeer onwaar.

16
00:00:51,350 --> 00:00:54,770
Dit is net te sê as ons 'n leë
skikking, waarde is duidelik nie in 'n

17
00:00:54,770 --> 00:00:57,860
leë skikking, sodat ons kan terugkeer onwaar.

18
00:00:57,860 --> 00:01:01,250
>> Nou, ons wil eintlik die binêre te doen
Soek deel van binêre soek.

19
00:01:01,250 --> 00:01:04,780
So, ons wil die middel te vind
element van hierdie reeks.

20
00:01:04,780 --> 00:01:09,130
Hier sê ons middel gelyk aan n verdeelde
deur 2, sedert die middel element is

21
00:01:09,130 --> 00:01:12,240
gaan die lengte van te wees
Ons verskeidenheid gedeel deur 2.

22
00:01:12,240 --> 00:01:15,040
Nou gaan ons kyk of die
Midde-element is gelyk aan die waarde wat ons is

23
00:01:15,040 --> 00:01:16,160
soek.

24
00:01:16,160 --> 00:01:21,030
So as waardes middel gelyk aan waarde, het ons
kan terugkeer waar nie, aangesien ons het die

25
00:01:21,030 --> 00:01:22,810
waarde in ons verskeidenheid.

26
00:01:22,810 --> 00:01:26,380
>> Maar as dit nie waar was nie, nou
Ons moet die rekursiewe te doen

27
00:01:26,380 --> 00:01:27,840
stap van binêre soek.

28
00:01:27,840 --> 00:01:30,450
Ons moet óf om te soek na die
links van die skikking of die

29
00:01:30,450 --> 00:01:32,320
middel van die skikking.

30
00:01:32,320 --> 00:01:39,280
So hier is, sê ons as waardes by die middel is
minder as waarde, wat beteken dat waarde

31
00:01:39,280 --> 00:01:41,350
groter as die middel was
van die skikking.

32
00:01:41,350 --> 00:01:45,790
So waarde moet aan die regterkant van die wees
element wat ons nou net gekyk.

33
00:01:45,790 --> 00:01:48,090
>> So hier gaan ons
soek rekursief.

34
00:01:48,090 --> 00:01:50,320
En ons sal sien wat ons verby
om dit in 'n tweede.

35
00:01:50,320 --> 00:01:53,440
Maar ons gaan soek na die
regs van die middel element.

36
00:01:53,440 --> 00:01:57,710
En in die ander geval is, wat beteken dat
waarde was minder as die helfte van die

37
00:01:57,710 --> 00:02:00,660
skikking, en so gaan ons
om te soek na die linkerkant.

38
00:02:00,660 --> 00:02:03,520
Nou, is die links gaan wees
'n bietjie makliker om te kyk na.

39
00:02:03,520 --> 00:02:07,770
So, hier sien ons dat ons rekursief
roep soek waar die eerste

40
00:02:07,770 --> 00:02:10,120
argument is, weer, die waarde
ons is op soek verby.

41
00:02:10,120 --> 00:02:14,970
Die tweede argument gaan wees om die
skikking wat ons is op soek verby.

42
00:02:14,970 --> 00:02:17,090
En die laaste element is nou middel.

43
00:02:17,090 --> 00:02:21,650
Onthou die laaste parameter is ons int
n, so dit is die lengte van ons verskeidenheid.

44
00:02:21,650 --> 00:02:25,310
>> In die rekursiewe oproep om te soek, ons is
nou te sê dat die lengte van die

45
00:02:25,310 --> 00:02:27,230
skikking is middel.

46
00:02:27,230 --> 00:02:32,900
So, as ons verskeidenheid was van grootte 20 en ons
deursoek indeks 10, sedert die middel is

47
00:02:32,900 --> 00:02:36,930
20 gedeel deur 2, wat beteken dat ons
verby 10 as die nuwe

48
00:02:36,930 --> 00:02:38,300
lengte van ons verskeidenheid.

49
00:02:38,300 --> 00:02:41,910
Onthou dat wanneer jy 'n verskeidenheid
'n lengte van 10, wat beteken dat die geldige

50
00:02:41,910 --> 00:02:45,450
elemente is in indekse 0 tot 9.

51
00:02:45,450 --> 00:02:50,120
So dit is presies wat ons wil
spesifiseer ons opgedateer verskeidenheid - die linker

52
00:02:50,120 --> 00:02:53,010
verskeidenheid van die middel element.

53
00:02:53,010 --> 00:02:55,710
>> So, op soek na die regte is
'n bietjie meer moeilik.

54
00:02:55,710 --> 00:03:00,170
Nou eers, laat ons kyk na die lengte
van die skikking aan die regterkant van die

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

56
00:03:01,240 --> 00:03:08,390
So, as ons verskeidenheid was van grootte n, dan is die
nuwe skikking sal van grootte n minus wees

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

58
00:03:10,140 --> 00:03:12,530
So, laat ons dink aan n minus middel.

59
00:03:12,530 --> 00:03:18,710
>> Weereens, as die skikking was van grootte 20 en
ons deur 2 die middel te kry,

60
00:03:18,710 --> 00:03:23,540
sodat die middel is 10, dan n minus middel
gaan gee ons 10, so 10

61
00:03:23,540 --> 00:03:25,330
elemente aan die regterkant van die middel.

62
00:03:25,330 --> 00:03:27,780
Maar ons het ook die minus
1, want ons wil nie

63
00:03:27,780 --> 00:03:29,700
sluit in die middel self.

64
00:03:29,700 --> 00:03:34,190
So n minus middel minus 1 gee ons die
totale aantal elemente aan die regterkant

65
00:03:34,190 --> 00:03:36,800
van die middel-indeks in die skikking.

66
00:03:36,800 --> 00:03:41,870
>> Nou hier, onthou dat die middel
parameter is die waardes skikking.

67
00:03:41,870 --> 00:03:46,180
So hier is ons verby 'n
opgedateer waardes skikking.

68
00:03:46,180 --> 00:03:50,930
Hierdie waardes plus middel plus 1 is
eintlik sê rekursief roep

69
00:03:50,930 --> 00:03:56,460
Soek, verby in 'n nuwe skikking, waar
dat die nuwe reeks begin in die middel

70
00:03:56,460 --> 00:03:59,370
plus een van ons oorspronklike waardes skikking.

71
00:03:59,370 --> 00:04:05,400
>> 'N alternatiewe sintaksis vir wat, nou dat
jy begin wysers te sien, is

72
00:04:05,400 --> 00:04:10,170
ampersand waardes middel plus 1.

73
00:04:10,170 --> 00:04:17,149
So, gryp die adres van die middel
plus een element van waardes.

74
00:04:17,149 --> 00:04:23,690
>> Nou, as jy nie gemaklik
wysiging van 'n skikking soos wat jy

75
00:04:23,690 --> 00:04:28,900
kon ook geïmplementeer hierdie gebruik
'n rekursiewe funksie helper, waar

76
00:04:28,900 --> 00:04:31,680
dat helper funksie neem
meer argumente.

77
00:04:31,680 --> 00:04:36,610
So in plaas van om net die waarde, die
skikking, en die grootte van die skikking,

78
00:04:36,610 --> 00:04:42,315
die helper funksie meer kan neem
argumente, insluitend die laer indeks

79
00:04:42,315 --> 00:04:45,280
wat jy sal omgee in die skikking
en die boonste indeks dat jy omgee

80
00:04:45,280 --> 00:04:46,300
oor die skikking.

81
00:04:46,300 --> 00:04:49,770
>> En so hou van beide die laer
indeks en die boonste indeks, wat jy doen nie

82
00:04:49,770 --> 00:04:52,780
nodig om ooit te verander
oorspronklike waardes skikking.

83
00:04:52,780 --> 00:04:56,390
Jy kan net voortgaan om te
Gebruik die waardes skikking.

84
00:04:56,390 --> 00:04:59,540
Maar hier, sien ons nie 'n hulp nodig het nie
funksioneer solank as wat ons is

85
00:04:59,540 --> 00:05:01,760
bereid is om die oorspronklike te verander
waardes skikking.

86
00:05:01,760 --> 00:05:05,020
Ons is bereid om te slaag in
'n updated waardes.

87
00:05:05,020 --> 00:05:09,140
>> Nou kan ons nie binêre soek oor
'n skikking wat ongesorteerde.

88
00:05:09,140 --> 00:05:12,220
So, laat ons kry dit uitgesorteer.

89
00:05:12,220 --> 00:05:17,650
Nou, sien dat die soort is afgelope twee
parameters int waardes, wat is die

90
00:05:17,650 --> 00:05:21,110
skikking wat ons sorteer, en int n,
wat is die lengte van die skikking wat

91
00:05:21,110 --> 00:05:22,250
ons sorteer.

92
00:05:22,250 --> 00:05:24,840
So, hier is ons wil implementeer
'n sorteeralgoritme

93
00:05:24,840 --> 00:05:26,690
wat o N vierkantig.

94
00:05:26,690 --> 00:05:30,560
Jy kan borrel soort, seleksie kies
soort, of voeg soort, of

95
00:05:30,560 --> 00:05:32,670
'n ander soort ons het nie
gesien in die klas.

96
00:05:32,670 --> 00:05:36,380
Maar hier, ons gaan
gebruik seleksie soort.

97
00:05:36,380 --> 00:05:40,030
>> So, gaan ons Itereer
oor die hele skikking.

98
00:05:40,030 --> 00:05:44,360
Wel, hier sien ons dat ons iterating
van 0 tot n minus 1.

99
00:05:44,360 --> 00:05:45,990
Hoekom nie al die pad tot n?

100
00:05:45,990 --> 00:05:49,320
Wel, die eerste as ons het reeds uitgesorteer
n minus 1 elemente, dan is die

101
00:05:49,320 --> 00:05:54,420
heel laaste element wat moet reeds
op die regte plek, so sorteer oor

102
00:05:54,420 --> 00:05:56,520
die hele skikking.

103
00:05:56,520 --> 00:05:58,770
>> Nou, onthou hoe seleksie
soort werk.

104
00:05:58,770 --> 00:06:01,950
Ons gaan om te gaan oor die hele skikking
soek na die minimum waarde in

105
00:06:01,950 --> 00:06:04,480
die skikking en stok wat
aan die begin.

106
00:06:04,480 --> 00:06:07,610
Daarna het ons gaan om te gaan oor die hele
skikking weer op soek na die tweede

107
00:06:07,610 --> 00:06:10,410
kleinste element, en die stok wat
in die tweede posisie in die

108
00:06:10,410 --> 00:06:12,100
skikking, en so aan.

109
00:06:12,100 --> 00:06:14,330
So, dit is wat dit is om te doen.

110
00:06:14,330 --> 00:06:17,290
>> Hier, ons sien dat ons
die opstel van die huidige minimum

111
00:06:17,290 --> 00:06:20,030
waarde tot die i-de-indeks.

112
00:06:20,030 --> 00:06:23,160
So op die eerste iterasie, ons gaan
oorweeg die minimum waarde te wees

113
00:06:23,160 --> 00:06:25,030
die begin van ons verskeidenheid.

114
00:06:25,030 --> 00:06:28,500
Dan gaan ons Itereer oor die
res van die skikking, monitor om te

115
00:06:28,500 --> 00:06:31,870
sien of daar enige elemente kleiner as
die een wat ons tans

116
00:06:31,870 --> 00:06:33,900
oorweging van die minimum te beperk.

117
00:06:33,900 --> 00:06:38,840
>> So hier, waardes j plus een - dit is
minder as wat ons tans

118
00:06:38,840 --> 00:06:40,380
oorweging van die minimum te beperk.

119
00:06:40,380 --> 00:06:42,940
Dan gaan ons te werk wat
ons dink is die minimum te

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

121
00:06:44,640 --> 00:06:48,540
So, doen wat oor die hele skikking,
en nadat dit vir lus, minimum

122
00:06:48,540 --> 00:06:53,160
moet die minimum element van
die i-de posisie in die skikking.

123
00:06:53,160 --> 00:06:57,350
>> Sodra ons het, kan ons ruil die
minimum waarde in die i-de posisie

124
00:06:57,350 --> 00:06:58,230
in die skikking.

125
00:06:58,230 --> 00:07:00,130
So dit is net 'n standaard ruil.

126
00:07:00,130 --> 00:07:03,940
Ons slaan in 'n tydelike waarde -
die i-de waarde van die skikking -

127
00:07:03,940 --> 00:07:08,460
sit in die i-de waarde in die skikking
minimum waarde dat daar hoort,

128
00:07:08,460 --> 00:07:13,580
en dan slaan terug in waar die
huidige minimum waarde wat gebruik word om die wees

129
00:07:13,580 --> 00:07:16,460
i-de waarde van die skikking, so
dat ons nie verloor nie.

130
00:07:16,460 --> 00:07:20,510
>> So, wat steeds op
die volgende iterasie.

131
00:07:20,510 --> 00:07:23,480
Ons sal begin soek na die tweede
minimum waarde en voeg wat in die

132
00:07:23,480 --> 00:07:24,590
tweede posisie.

133
00:07:24,590 --> 00:07:27,440
Op die derde iterasie, sal ons kyk vir
die derde minimum waarde en voeg

134
00:07:27,440 --> 00:07:31,550
wat in die derde posisie, en so
totdat ons 'n gesorteerde skikking.

135
00:07:31,550 --> 00:07:33,820
My naam is Rob, en hierdie
was seleksie soort.

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