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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Hej, jeg er Rob.

3
00:00:15,010 --> 00:00:16,790
Hvordan kan vi ansætte en binær søgning?

4
00:00:16,790 --> 00:00:18,770
Lad os finde ud af.

5
00:00:18,770 --> 00:00:23,400
Så bemærk, at denne søgning vil vi
at gennemføre rekursivt.

6
00:00:23,400 --> 00:00:27,470
Du kan også gennemføre binær søgning
iterativt, så hvis du gjorde det,

7
00:00:27,470 --> 00:00:29,280
det er helt fint.

8
00:00:29,280 --> 00:00:32,820
>> Nu først, lad os huske på, hvad
parametre til søgningen er beregnet til at være.

9
00:00:32,820 --> 00:00:36,120
Her ser vi int værdi, hvilket er
formodes at være den værdi, brugeren er

10
00:00:36,120 --> 00:00:37,320
søger efter.

11
00:00:37,320 --> 00:00:40,800
Vi ser int værdier array, som
er den matrix, som vi er

12
00:00:40,800 --> 00:00:42,520
søger efter værdi.

13
00:00:42,520 --> 00:00:45,602
Og vi ser int n, som er
længden af ​​vores array.

14
00:00:45,602 --> 00:00:47,410
>> Nu første først.

15
00:00:47,410 --> 00:00:51,350
Vi tjekker for at se, hvis n er lig med 0, i
hvilket tilfælde vi vender tilbage falsk.

16
00:00:51,350 --> 00:00:54,770
Det er bare at sige, hvis vi har en tom
array, værdien er helt klart ikke et

17
00:00:54,770 --> 00:00:57,860
tom array, så vi kan vende tilbage falsk.

18
00:00:57,860 --> 00:01:01,250
>> Nu vi faktisk ønsker at gøre den binære
søgning del af binær søgning.

19
00:01:01,250 --> 00:01:04,780
Så vi ønsker at finde den midterste
element i denne matrix.

20
00:01:04,780 --> 00:01:09,130
Her siger vi midt lig n delt
med 2, idet den midterste element er

21
00:01:09,130 --> 00:01:12,240
vil være længden af
vores matrix divideres med 2.

22
00:01:12,240 --> 00:01:15,040
Nu skal vi til at tjekke for at se, om
midterste element lig med den værdi, vi er

23
00:01:15,040 --> 00:01:16,160
søger efter.

24
00:01:16,160 --> 00:01:21,030
Så hvis værdier midten er lig værdi, vi
kan returnere sandt, da vi fandt

25
00:01:21,030 --> 00:01:22,810
værdi i vores array.

26
00:01:22,810 --> 00:01:26,380
>> Men hvis det ikke var sandt, nu
vi nødt til at gøre den rekursive

27
00:01:26,380 --> 00:01:27,840
trin i binær søgning.

28
00:01:27,840 --> 00:01:30,450
Vi er nødt til at søge til enten den
venstre for matrix eller til

29
00:01:30,450 --> 00:01:32,320
midten af ​​arrayet.

30
00:01:32,320 --> 00:01:39,280
Så her, siger vi, hvis værdier i midten er
mindre end værdien, der betyder, at værdien

31
00:01:39,280 --> 00:01:41,350
var større end den midterste
af matrixen.

32
00:01:41,350 --> 00:01:45,790
Så værdi skal være til højre for
element, som vi lige har set på.

33
00:01:45,790 --> 00:01:48,090
>> Så her, vi kommer til at
søg rekursivt.

34
00:01:48,090 --> 00:01:50,320
Og vi vil se på, hvad vi passerer
til dette i en anden.

35
00:01:50,320 --> 00:01:53,440
Men vi kommer til at søge til
ret af den midterste element.

36
00:01:53,440 --> 00:01:57,710
Og i det andet tilfælde, der betyder, at
værdien var mindre end i midten af

37
00:01:57,710 --> 00:02:00,660
array, og så vil vi
at søge til venstre.

38
00:02:00,660 --> 00:02:03,520
Nu er venstre vil være
lidt nemmere at se på.

39
00:02:03,520 --> 00:02:07,770
Så vi ser her, at vi er rekursivt
ringer søgning, hvor den første

40
00:02:07,770 --> 00:02:10,120
argument er, igen, værdien
vi kigger forbi.

41
00:02:10,120 --> 00:02:14,970
Det andet argument vil være den
array, vi søger forbi.

42
00:02:14,970 --> 00:02:17,090
Og det sidste element er nu midten.

43
00:02:17,090 --> 00:02:21,650
Husk den sidste parameter er vores int
n, så det er længden af ​​vores array.

44
00:02:21,650 --> 00:02:25,310
>> I det rekursive kald til at søge, er vi
siger nu, at længden af ​​den

45
00:02:25,310 --> 00:02:27,230
array er midten.

46
00:02:27,230 --> 00:02:32,900
Så hvis vores vifte var størrelse 20 og vi
søgte på indeks 10, da midten er

47
00:02:32,900 --> 00:02:36,930
20 divideret med 2, der betyder, at vi
passerer 10 som den nye

48
00:02:36,930 --> 00:02:38,300
længden af ​​vores array.

49
00:02:38,300 --> 00:02:41,910
Husk, at når du har en array
af længde 10, betyder det gyldige

50
00:02:41,910 --> 00:02:45,450
elementer er i indeks 0 til 9.

51
00:02:45,450 --> 00:02:50,120
Så dette er præcis, hvad vi ønsker at
specificere vores opdaterede array - venstre

52
00:02:50,120 --> 00:02:53,010
matrix fra midten element.

53
00:02:53,010 --> 00:02:55,710
>> Så ser til højre er
en smule mere vanskeligt.

54
00:02:55,710 --> 00:03:00,170
Nu først, lad os overveje længden
af arrayet til højre for

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

56
00:03:01,240 --> 00:03:08,390
Så hvis vores vifte var størrelse n, så
nyt array vil være af størrelse n minus

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

58
00:03:10,140 --> 00:03:12,530
Så lad os tænke på n minus midten.

59
00:03:12,530 --> 00:03:18,710
>> Igen, hvis matrixen var størrelse 20 og
vi dividere med 2 for at få midten,

60
00:03:18,710 --> 00:03:23,540
så midten er 10, så n minus midten
vil give os 10, så 10

61
00:03:23,540 --> 00:03:25,330
elementer til højre for midten.

62
00:03:25,330 --> 00:03:27,780
Men vi har også denne minus
1, da vi ikke ønsker at

63
00:03:27,780 --> 00:03:29,700
omfatte midten selv.

64
00:03:29,700 --> 00:03:34,190
Så n minus midten minus 1 giver os
samlede antal elementer til højre

65
00:03:34,190 --> 00:03:36,800
af den midterste indeks i array.

66
00:03:36,800 --> 00:03:41,870
>> Nu her huske på, at den midterste
parameter er værdier array.

67
00:03:41,870 --> 00:03:46,180
Så her er vi passerer en
opdaterede værdier array.

68
00:03:46,180 --> 00:03:50,930
Denne værdier plus midterste plus 1 er
faktisk siger rekursivt kalde

69
00:03:50,930 --> 00:03:56,460
søgning, der passerer i en ny matrix, hvor
at nyt array starter i midten

70
00:03:56,460 --> 00:03:59,370
plus én af vores oprindelige værdier array.

71
00:03:59,370 --> 00:04:05,400
>> En alternativ syntaks for, at nu hvor
du er begyndt at se pegepinde, er

72
00:04:05,400 --> 00:04:10,170
Ampersand værdier midterste plus 1.

73
00:04:10,170 --> 00:04:17,149
Så tag fat i adressen på den midterste
plus en del af værdier.

74
00:04:17,149 --> 00:04:23,690
>> Nu, hvis du ikke var komfortable
modificere et array som, du

75
00:04:23,690 --> 00:04:28,900
kunne også have gennemført denne hjælp
en rekursiv hjælpefunktion, hvor

76
00:04:28,900 --> 00:04:31,680
at hjælperen funktion tager
flere argumenter.

77
00:04:31,680 --> 00:04:36,610
Så i stedet for at tage bare den værdi,
array, og størrelsen af ​​array,

78
00:04:36,610 --> 00:04:42,315
den hjælpefunktion kunne tage mere
argumenter, herunder lavere indeks

79
00:04:42,315 --> 00:04:45,280
at du ville bekymre sig om i array
og den øvre indeks, som du holder af

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

81
00:04:46,300 --> 00:04:49,770
>> Og så holde styr på både den lave
indekset og øvre indeks, behøver du ikke

82
00:04:49,770 --> 00:04:52,780
nødt til nogensinde ændre
oprindelige værdier array.

83
00:04:52,780 --> 00:04:56,390
Du kan bare fortsætte med at
bruge værdierne array.

84
00:04:56,390 --> 00:04:59,540
Men her, bemærker vi ikke brug for en hjælper
fungere, så længe vi er

85
00:04:59,540 --> 00:05:01,760
villig til at ændre den oprindelige
værdier array.

86
00:05:01,760 --> 00:05:05,020
Vi er villige til at passere i
en opdaterede værdier.

87
00:05:05,020 --> 00:05:09,140
>> Nu kan vi ikke binær Søg igen
et array, der er usorteret.

88
00:05:09,140 --> 00:05:12,220
Så lad os få dette løst.

89
00:05:12,220 --> 00:05:17,650
Nu bemærke, at slags er forbi to
parametre int værdier, som er

90
00:05:17,650 --> 00:05:21,110
array, vi sortering og int n,
som er længden af ​​array,

91
00:05:21,110 --> 00:05:22,250
vi sortering.

92
00:05:22,250 --> 00:05:24,840
Så her vi ønsker at gennemføre
en sorteringsalgoritme

93
00:05:24,840 --> 00:05:26,690
der er o n potens.

94
00:05:26,690 --> 00:05:30,560
Du kan vælge boble sortere, udvælgelse
sortere, eller indsættelse slags, eller

95
00:05:30,560 --> 00:05:32,670
nogle andre slags vi ikke har
set i klassen.

96
00:05:32,670 --> 00:05:36,380
Men her, vi kommer til at
bruge udvælgelse slags.

97
00:05:36,380 --> 00:05:40,030
>> Så vi kommer til at gentage
over hele systemet.

98
00:05:40,030 --> 00:05:44,360
Nå, her ser vi, at vi iteration
fra 0 til n minus 1.

99
00:05:44,360 --> 00:05:45,990
Hvorfor ikke hele vejen op til n?

100
00:05:45,990 --> 00:05:49,320
Tja, hvis vi allerede har sorteret det første
n minus 1 elementer, så

101
00:05:49,320 --> 00:05:54,420
meget sidste element, hvad allerede skal
på det rigtige sted, så sortering i

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

103
00:05:56,520 --> 00:05:58,770
>> Nu huske, hvordan valg
slags virker.

104
00:05:58,770 --> 00:06:01,950
Vi kommer til at gå over hele systemet
udkig efter den mindste værdi på

105
00:06:01,950 --> 00:06:04,480
array og stok, der
i begyndelsen.

106
00:06:04,480 --> 00:06:07,610
Så vi kommer til at gå over hele
matrix igen på udkig efter den anden

107
00:06:07,610 --> 00:06:10,410
mindste element, og stok, der
i den anden position i

108
00:06:10,410 --> 00:06:12,100
array, og så videre.

109
00:06:12,100 --> 00:06:14,330
Så det er, hvad det gør.

110
00:06:14,330 --> 00:06:17,290
>> Her ser vi, at vi er
sætte den nuværende minimum

111
00:06:17,290 --> 00:06:20,030
værdi for den i'te indeks.

112
00:06:20,030 --> 00:06:23,160
Så på den første iteration, vil vi
at undersøge den mindste værdi for at være

113
00:06:23,160 --> 00:06:25,030
starten af ​​vores array.

114
00:06:25,030 --> 00:06:28,500
Så vi kommer til at gentage over den
resten af ​​arrayet, kontrol for

115
00:06:28,500 --> 00:06:31,870
se, om der nogen elementer mindre end
den ene, som vi i øjeblikket

116
00:06:31,870 --> 00:06:33,900
overvejer minimum.

117
00:06:33,900 --> 00:06:38,840
>> Så her, værdier j plus én - det er
mindre end hvad vi er i øjeblikket

118
00:06:38,840 --> 00:06:40,380
overvejer minimum.

119
00:06:40,380 --> 00:06:42,940
Så vi kommer til at opdatere hvad
vi synes er minimum for at

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

121
00:06:44,640 --> 00:06:48,540
Så gør det på tværs af hele array,
og efter denne for-løkke, minimum

122
00:06:48,540 --> 00:06:53,160
bør være det mindste element fra
den i'te position i arrayet.

123
00:06:53,160 --> 00:06:57,350
>> Når vi har det, kan vi bytte
mindste værdi i den i'te position

124
00:06:57,350 --> 00:06:58,230
i array'et.

125
00:06:58,230 --> 00:07:00,130
Så dette er blot en standard swap.

126
00:07:00,130 --> 00:07:03,940
Vi gemmer i en midlertidig værdi -
den i'te værdi i array -

127
00:07:03,940 --> 00:07:08,460
sat i den i'te værdi i array
minimumsværdi, der hører der,

128
00:07:08,460 --> 00:07:13,580
og derefter gemme tilbage til hvor
nuværende minimum værdi plejede at være

129
00:07:13,580 --> 00:07:16,460
i'te værdi i matrixen, så
at vi ikke mister den.

130
00:07:16,460 --> 00:07:20,510
>> Så det fortsætter på
den næste iteration.

131
00:07:20,510 --> 00:07:23,480
Vi vil begynde at lede efter den anden
mindste værdi og indsætte det i

132
00:07:23,480 --> 00:07:24,590
anden position.

133
00:07:24,590 --> 00:07:27,440
På den tredje iteration, vil vi se efter
den tredje mindste værdi og indsæt

134
00:07:27,440 --> 00:07:31,550
der ind i tredje position, og så
på, indtil vi har en sorteret array.

135
00:07:31,550 --> 00:07:33,820
Mit navn er Rob, og dette
var valg slags.

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