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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Hoi, ik ben Rob.

3
00:00:15,010 --> 00:00:16,790
Hoe kunnen we gebruik van een binary search?

4
00:00:16,790 --> 00:00:18,770
Laten we eens kijken.

5
00:00:18,770 --> 00:00:23,400
Dus, er rekening mee dat deze zoekopdracht gaan we
recursief uitvoeren.

6
00:00:23,400 --> 00:00:27,470
Je zou binary search ook uitvoering
iteratief, dus als je dat deed,

7
00:00:27,470 --> 00:00:29,280
dat is prima.

8
00:00:29,280 --> 00:00:32,820
>> Nu laten we eerst eens herinneren wat de
parameters te zoeken zijn bedoeld om te worden.

9
00:00:32,820 --> 00:00:36,120
Hier zien we int waarde, die
moet de waarde de gebruiker zijn

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

11
00:00:37,320 --> 00:00:40,800
We zien de int waarden array, die
is de array waarin we

12
00:00:40,800 --> 00:00:42,520
op zoek naar waarde.

13
00:00:42,520 --> 00:00:45,602
En we zien int n, dat is
de lengte van onze array.

14
00:00:45,602 --> 00:00:47,410
>> Nu, het eerste wat eerst.

15
00:00:47,410 --> 00:00:51,350
Wij controleren om te zien of n gelijk is aan 0, in
welk geval we return false.

16
00:00:51,350 --> 00:00:54,770
Dat is gewoon te zeggen als we een leeg
array waarde duidelijk niet per

17
00:00:54,770 --> 00:00:57,860
lege array, dus we kunnen return false.

18
00:00:57,860 --> 00:01:01,250
>> Nu, we eigenlijk willen de binaire doen
zoek een deel van binaire zoeken.

19
00:01:01,250 --> 00:01:04,780
Dus, we willen naar het midden te vinden
element van deze array.

20
00:01:04,780 --> 00:01:09,130
Hier zeggen we midden gelijk aan n verdeeld
met 2, aangezien het middelste element

21
00:01:09,130 --> 00:01:12,240
naar de lengte zijn van
ons aanbod gedeeld door 2.

22
00:01:12,240 --> 00:01:15,040
Nu gaan we om te controleren om te zien of de
middelste element is gelijk aan de waarde die wij zijn

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

24
00:01:16,160 --> 00:01:21,030
Dus als waarden midden gelijk waarde, we
waar kan terugkeren omdat we vonden de

25
00:01:21,030 --> 00:01:22,810
waarde in onze array.

26
00:01:22,810 --> 00:01:26,380
>> Maar als dat niet zo was, nu
moeten we de recursieve doen

27
00:01:26,380 --> 00:01:27,840
stap van binary search.

28
00:01:27,840 --> 00:01:30,450
We moeten ofwel zoeken naar de
links van de matrix of de

29
00:01:30,450 --> 00:01:32,320
midden van de array.

30
00:01:32,320 --> 00:01:39,280
Dus hier, zeggen we als waarden op midden is
minder dan de waarde, dat wil zeggen dat de waarde

31
00:01:39,280 --> 00:01:41,350
was groter dan het midden
van de array.

32
00:01:41,350 --> 00:01:45,790
Dus moet waarde aan de rechterkant van de
element dat we gewoon gekeken.

33
00:01:45,790 --> 00:01:48,090
>> Dus hier gaan we naar
zoeken recursief.

34
00:01:48,090 --> 00:01:50,320
En kijken we naar wat we passeren
deze in een tweede.

35
00:01:50,320 --> 00:01:53,440
Maar we gaan zoeken naar de
rechts van het middelste element.

36
00:01:53,440 --> 00:01:57,710
En in het andere geval, dat betekent dat
waarde lager dan het midden van de was

37
00:01:57,710 --> 00:02:00,660
array, en dus we gaan
te zoeken naar links.

38
00:02:00,660 --> 00:02:03,520
Nu, de linker gaat worden
een stuk makkelijker om naar te kijken.

39
00:02:03,520 --> 00:02:07,770
Zo zien we hier dat we recursief
waar de eerste bellen zoekopdracht

40
00:02:07,770 --> 00:02:10,120
argument weer, de waarde
we kijken voorbij.

41
00:02:10,120 --> 00:02:14,970
Het tweede argument gaat worden de
array die we op zoek waren voorbij.

42
00:02:14,970 --> 00:02:17,090
En het laatste element is nu midden.

43
00:02:17,090 --> 00:02:21,650
Denk aan de laatste parameter is onze int
n, dus dat is de lengte van ons aanbod.

44
00:02:21,650 --> 00:02:25,310
>> In de recursieve oproep om te zoeken, we zijn
nu dat de lengte van de

45
00:02:25,310 --> 00:02:27,230
array is midden.

46
00:02:27,230 --> 00:02:32,900
Dus, als ons aanbod was van maat 20 en we
gezocht bij index 10, sinds midden is

47
00:02:32,900 --> 00:02:36,930
20 gedeeld door 2, dat betekent dat we
10 langs de nieuwe

48
00:02:36,930 --> 00:02:38,300
lengte van onze array.

49
00:02:38,300 --> 00:02:41,910
Vergeet niet dat als je een array
lengte 10, dat betekent de geldige

50
00:02:41,910 --> 00:02:45,450
elementen in indices 0 tot 9.

51
00:02:45,450 --> 00:02:50,120
Dus dit is precies wat we willen
specificeren onze vernieuwde serie - links

52
00:02:50,120 --> 00:02:53,010
matrix van het midden element.

53
00:02:53,010 --> 00:02:55,710
>> Dus, op zoek naar de juiste is
een beetje moeilijker.

54
00:02:55,710 --> 00:03:00,170
Nu laten we eerst eens kijken naar de lengte
van de matrix rechts van de

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

56
00:03:01,240 --> 00:03:08,390
Dus, als ons aanbod was van grootte n, dan is de
nieuwe array van grootte n minus zijn

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

58
00:03:10,140 --> 00:03:12,530
Dus, laten we denken aan n minus midden.

59
00:03:12,530 --> 00:03:18,710
>> Ook als de array waren van grootte 20 en
we delen door 2 naar het midden te krijgen,

60
00:03:18,710 --> 00:03:23,540
dus het midden is 10, dan is n minus midden
gaat om ons 10, dus 10

61
00:03:23,540 --> 00:03:25,330
elementen rechts van het midden.

62
00:03:25,330 --> 00:03:27,780
Maar we hebben ook dit minus
1, omdat we niet willen

63
00:03:27,780 --> 00:03:29,700
onder het midden zelf.

64
00:03:29,700 --> 00:03:34,190
Zo n minus midden minus 1 geeft ons de
totale aantal elementen rechts

65
00:03:34,190 --> 00:03:36,800
de middelste index in de array.

66
00:03:36,800 --> 00:03:41,870
>> Nu hier, bedenk dan dat het midden
parameter waarden matrix.

67
00:03:41,870 --> 00:03:46,180
Dus hier, we passeren een
bijgewerkte waarden array.

68
00:03:46,180 --> 00:03:50,930
Deze waarden plus midden plus 1 is
eigenlijk zeggen recursief bellen

69
00:03:50,930 --> 00:03:56,460
zoeken, passeren in een nieuwe array, waar
dat nieuwe array begint in het midden

70
00:03:56,460 --> 00:03:59,370
plus een van onze oorspronkelijke waarden array.

71
00:03:59,370 --> 00:04:05,400
>> Een alternatieve syntax voor dat, nu
je bent begonnen met pointers te zien, is

72
00:04:05,400 --> 00:04:10,170
ampersand waarden midden plus 1.

73
00:04:10,170 --> 00:04:17,149
Dus, pak het adres van de middelste
plus een element van waarden.

74
00:04:17,149 --> 00:04:23,690
>> Nu, als je niet comfortabel
het wijzigen van een array als dat, je

75
00:04:23,690 --> 00:04:28,900
kon ook hebben geïmplementeerd dit met behulp van
een recursieve helper functie, waarbij

76
00:04:28,900 --> 00:04:31,680
dat helper functie neemt
meer argumenten.

77
00:04:31,680 --> 00:04:36,610
Dus in plaats van alleen de waarde, de
matrix en de grootte van de matrix,

78
00:04:36,610 --> 00:04:42,315
de helper functie kan langer duren
argumenten, waaronder de lagere index

79
00:04:42,315 --> 00:04:45,280
dat je over zou geven in de array
en de bovenste index die u geeft

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

81
00:04:46,300 --> 00:04:49,770
>> En dus het bijhouden van zowel de lagere
index en de hogere index, u niet

82
00:04:49,770 --> 00:04:52,780
moet ooit wijzigen de
oorspronkelijke waarden array.

83
00:04:52,780 --> 00:04:56,390
Je kunt gewoon blijven
Gebruik de waarden array.

84
00:04:56,390 --> 00:04:59,540
Maar hier zien we geen helper nodig
functioneren zolang we

85
00:04:59,540 --> 00:05:01,760
bereid om het origineel te wijzigen
waarden array.

86
00:05:01,760 --> 00:05:05,020
We zijn bereid om in de pas
een bijgewerkte waarden.

87
00:05:05,020 --> 00:05:09,140
>> Nu kunnen we niet binary search boven
een array die is ongesorteerd.

88
00:05:09,140 --> 00:05:12,220
Dus, laten we dit uitgezocht.

89
00:05:12,220 --> 00:05:17,650
Merk nu op dat soort is afgelopen twee
parameters int waarden, die de

90
00:05:17,650 --> 00:05:21,110
array die we sorteren en int n,
dat de lengte van de array die

91
00:05:21,110 --> 00:05:22,250
we sorteren.

92
00:05:22,250 --> 00:05:24,840
Dus, hier willen we de uitvoering van
een sorteer-algoritme

93
00:05:24,840 --> 00:05:26,690
die o n kwadraat.

94
00:05:26,690 --> 00:05:30,560
Je kon bubble sort, selectie kiezen
sorteren of insertion sort of

95
00:05:30,560 --> 00:05:32,670
een ander soort hebben we niet
gezien in de klas.

96
00:05:32,670 --> 00:05:36,380
Maar hier, we gaan
Gebruik selectie sorteren.

97
00:05:36,380 --> 00:05:40,030
>> Dus, we gaan herhalen
over de gehele array.

98
00:05:40,030 --> 00:05:44,360
Nou, hier zien we dat we itereren
van 0 tot n minus 1.

99
00:05:44,360 --> 00:05:45,990
Waarom niet de hele weg tot aan n?

100
00:05:45,990 --> 00:05:49,320
Nou, als we al naargelang de eerste
n minus 1 elementen, vervolgens de

101
00:05:49,320 --> 00:05:54,420
laatste element wat er al moeten zijn
op de juiste plaats, zodat het sorteren op

102
00:05:54,420 --> 00:05:56,520
de hele array.

103
00:05:56,520 --> 00:05:58,770
>> Nu bedenk hoe selectie
sort werkt.

104
00:05:58,770 --> 00:06:01,950
We gaan te gaan over de hele array
zoekt de minimale waarde

105
00:06:01,950 --> 00:06:04,480
de array en stok die
aan het begin.

106
00:06:04,480 --> 00:06:07,610
Dan gaan we te gaan over de gehele
serie opnieuw op zoek naar de tweede

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

108
00:06:10,410 --> 00:06:12,100
matrix, enzovoort.

109
00:06:12,100 --> 00:06:14,330
Dus, dat is wat dit doet.

110
00:06:14,330 --> 00:06:17,290
>> Hier, we zien dat we
het instellen van de huidige minimale

111
00:06:17,290 --> 00:06:20,030
waarde voor de i-de index.

112
00:06:20,030 --> 00:06:23,160
Dus op de eerste iteratie, we gaan
overwegen de minimumwaarde te

113
00:06:23,160 --> 00:06:25,030
het begin van ons aanbod.

114
00:06:25,030 --> 00:06:28,500
Dan gaan we itereren over de
rest van de array te controleren

115
00:06:28,500 --> 00:06:31,870
zien of er elementen kleiner dan
degene die we momenteel

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

117
00:06:33,900 --> 00:06:38,840
>> Dus hier, waarden j plus een - dat is
minder dan wat we momenteel

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

119
00:06:40,380 --> 00:06:42,940
Dan gaan we werken wat
we denken dat is het minimum om

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

121
00:06:44,640 --> 00:06:48,540
Dus doen over de hele array,
en na deze lus, minimum

122
00:06:48,540 --> 00:06:53,160
moet de minimale element van
het i-de positie in de array.

123
00:06:53,160 --> 00:06:57,350
>> Zodra we dat, kunnen we ruilen de
minimale waarde in de i-de positie

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

125
00:06:58,230 --> 00:07:00,130
Dus dit is gewoon een standaard swap.

126
00:07:00,130 --> 00:07:03,940
We slaan in een tijdelijke waarde -
de i-de waarde in de matrix -

127
00:07:03,940 --> 00:07:08,460
steken in de i-de waarde in de matrix de
minimumwaarde dat er behoort,

128
00:07:08,460 --> 00:07:13,580
en vervolgens op te slaan terug naar waar het
stroom gebruikt om de te minimumwaarde

129
00:07:13,580 --> 00:07:16,460
i-de waarde in de matrix, zodat
dat we niet verliezen.

130
00:07:16,460 --> 00:07:20,510
>> Zo, die nog steeds op
de volgende iteratie.

131
00:07:20,510 --> 00:07:23,480
We gaan op zoek naar de tweede
minimumwaarde en steek die in de

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

133
00:07:24,590 --> 00:07:27,440
Op de derde iteratie, zullen we kijken naar
de derde minimale waarde en insert

134
00:07:27,440 --> 00:07:31,550
dat naar de derde positie, en dus
op tot we een gesorteerde array.

135
00:07:31,550 --> 00:07:33,820
Mijn naam is Rob, en dit
was selectie sorteren.

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