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

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

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

4
00:00:16,790 --> 00:00:18,770
La oss finne det ut.

5
00:00:18,770 --> 00:00:23,400
Så, merk at dette søket skal vi
å gjennomføre rekursivt.

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

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

8
00:00:29,280 --> 00:00:32,820
>> Nå først, la oss huske hva
parametere for å søke er ment å være.

9
00:00:32,820 --> 00:00:36,120
Her ser vi int verdi, som er
ment å være den verdien brukeren

10
00:00:36,120 --> 00:00:37,320
søker etter.

11
00:00:37,320 --> 00:00:40,800
Vi ser int verdier array, som
er matrisen der er vi

12
00:00:40,800 --> 00:00:42,520
søker etter verdi.

13
00:00:42,520 --> 00:00:45,602
Og vi ser int n, som er
lengden på rekken.

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

15
00:00:47,410 --> 00:00:51,350
Vi sjekker for å se om n er lik 0, i
hvilket tilfelle vi return false.

16
00:00:51,350 --> 00:00:54,770
Det er bare å si at hvis vi har en tom
array, verdien er åpenbart ikke i en

17
00:00:54,770 --> 00:00:57,860
tom array, slik at vi kan returnere false.

18
00:00:57,860 --> 00:01:01,250
>> Nå, vi faktisk ønsker å gjøre det binære
søk del av binære søk.

19
00:01:01,250 --> 00:01:04,780
Så ønsker vi å finne midten
element i denne matrise.

20
00:01:04,780 --> 00:01:09,130
Her sier vi midt lik n delt
med 2, siden midten element er

21
00:01:09,130 --> 00:01:12,240
kommer til å være lengden
vårt spekter delt på to.

22
00:01:12,240 --> 00:01:15,040
Nå skal vi sjekke for å se om
midtre element tilsvarer verdien vi er

23
00:01:15,040 --> 00:01:16,160
søker etter.

24
00:01:16,160 --> 00:01:21,030
Så hvis verdier midten lik verdi, vi
kan returnere sant siden vi fant

25
00:01:21,030 --> 00:01:22,810
verdi i vårt utvalg.

26
00:01:22,810 --> 00:01:26,380
>> Men hvis det ikke var sant, nå
vi trenger for å gjøre den rekursive

27
00:01:26,380 --> 00:01:27,840
trinn av binære søk.

28
00:01:27,840 --> 00:01:30,450
Vi trenger å søke enten til
venstre for matrisen eller til

29
00:01:30,450 --> 00:01:32,320
midten av tabellen.

30
00:01:32,320 --> 00:01:39,280
Så her sier vi om verdier på midten er
mindre enn verdien, det betyr at verdi

31
00:01:39,280 --> 00:01:41,350
var større enn i midten
i matrisen.

32
00:01:41,350 --> 00:01:45,790
Så verdien må være til høyre for
element som vi bare så på.

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

34
00:01:48,090 --> 00:01:50,320
Og vi vil se på hva vi passerer
til dette i et sekund.

35
00:01:50,320 --> 00:01:53,440
Men vi kommer til å søke til
høyre for midtelementet.

36
00:01:53,440 --> 00:01:57,710
Og i det andre tilfellet, det betyr at
-verdien var lavere enn midten av

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

38
00:02:00,660 --> 00:02:03,520
Nå, er venstre kommer til å bli
litt lettere å se på.

39
00:02:03,520 --> 00:02:07,770
Så ser vi her at vi er rekursivt
ringer søk der først

40
00:02:07,770 --> 00:02:10,120
argumentet er, igjen, verdien
vi ser over.

41
00:02:10,120 --> 00:02:14,970
Det andre argumentet kommer til å være det
array som vi skulle søke over.

42
00:02:14,970 --> 00:02:17,090
Og det siste elementet er nå midten.

43
00:02:17,090 --> 00:02:21,650
Husk den siste parameteren er vår int
n, slik at det er lengden på rekken.

44
00:02:21,650 --> 00:02:25,310
>> I den rekursive kall til å søke, vi er
nå si at lengden av

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

46
00:02:27,230 --> 00:02:32,900
Så, hvis vår rekke var av størrelse 20, og vi
søkte på indeksen 10, siden midten er

47
00:02:32,900 --> 00:02:36,930
20 delt på to, betyr at vi er
passerer 10 som ny

48
00:02:36,930 --> 00:02:38,300
lengden på array.

49
00:02:38,300 --> 00:02:41,910
Husk at når du har en matrise
av lengde 10, betyr at den gyldige

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

51
00:02:45,450 --> 00:02:50,120
Så dette er akkurat hva vi ønsker å
spesifisere vår oppdaterte utvalg - venstre

52
00:02:50,120 --> 00:02:53,010
matrisen fra det midtre element.

53
00:02:53,010 --> 00:02:55,710
>> Så, ser til høyre er
litt vanskeligere.

54
00:02:55,710 --> 00:03:00,170
Nå først, la oss vurdere lengden
i matrisen til høyre for

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

56
00:03:01,240 --> 00:03:08,390
Så, hvis vår rekke var av størrelse n, deretter
nye utvalget vil være av størrelse n minus

57
00:03:08,390 --> 00:03:10,140
midten minus en.

58
00:03:10,140 --> 00:03:12,530
Så, la oss tenke på n minus midten.

59
00:03:12,530 --> 00:03:18,710
>> Igjen, dersom matrisen var av størrelse 20 og
Vi deler med 2 for å få midten,

60
00:03:18,710 --> 00:03:23,540
så midten er 10, deretter n minus midten
kommer til å gi oss 10, så 10

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

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

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

64
00:03:29,700 --> 00:03:34,190
Så n minus midten minus 1 gir oss
totalt antall elementer til høyre

65
00:03:34,190 --> 00:03:36,800
av midten indeksen i matrisen.

66
00:03:36,800 --> 00:03:41,870
>> Nå her, husk at midten
parameter er verdiene array.

67
00:03:41,870 --> 00:03:46,180
Så her er vi passerer en
oppdaterte verdier array.

68
00:03:46,180 --> 00:03:50,930
Dette verdier pluss midten pluss en er
faktisk sier rekursivt ringe

69
00:03:50,930 --> 00:03:56,460
søk, passerer i en ny rekke, der
den nye matrisen begynner i midten

70
00:03:56,460 --> 00:03:59,370
pluss en av vår opprinnelige verdier array.

71
00:03:59,370 --> 00:04:05,400
>> En alternativ syntaks for det, nå som
du har begynt å se pekere, er

72
00:04:05,400 --> 00:04:10,170
Ampersand verdier midten pluss en.

73
00:04:10,170 --> 00:04:17,149
Så, ta tak i adressen til midten
plus en del av verdier.

74
00:04:17,149 --> 00:04:23,690
>> Nå, hvis du ikke var komfortable
modifisere en matrise som det, du

75
00:04:23,690 --> 00:04:28,900
kunne også ha implementert dette ved hjelp
en rekursiv hjelpefunksjon, der

76
00:04:28,900 --> 00:04:31,680
som hjelper funksjon tar
flere argumenter.

77
00:04:31,680 --> 00:04:36,610
Så i stedet for å ta akkurat den verdien,
matrisen og størrelsen av matrisen,

78
00:04:36,610 --> 00:04:42,315
hjelperen funksjonen kunne ta mer
argumentasjon, inklusive lavere indeks

79
00:04:42,315 --> 00:04:45,280
at du ville bry seg om i matrisen
og den øvre indeksen at du bryr deg

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

81
00:04:46,300 --> 00:04:49,770
>> Og så holder styr på både lavere
indeksen og den øvre indeks, gjør du ikke

82
00:04:49,770 --> 00:04:52,780
trenger å stadig endre
opprinnelige verdiene array.

83
00:04:52,780 --> 00:04:56,390
Du kan bare fortsette å
bruke verdiene array.

84
00:04:56,390 --> 00:04:59,540
Men her ser vi ikke trenger en hjelper
fungere så lenge vi er

85
00:04:59,540 --> 00:05:01,760
villig til å modifisere den opprinnelige
verdier array.

86
00:05:01,760 --> 00:05:05,020
Vi er villig til å passere i
en oppdatert verdier.

87
00:05:05,020 --> 00:05:09,140
>> Nå kan vi ikke binære søk på
en matrise som er usortert.

88
00:05:09,140 --> 00:05:12,220
Så, la oss få dette sortert ut.

89
00:05:12,220 --> 00:05:17,650
Nå merker den slags er forbi to
parametre int verdier, som er den

90
00:05:17,650 --> 00:05:21,110
array som vi sortering, og int n,
som er lengden av den matrise som

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

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

93
00:05:24,840 --> 00:05:26,690
som er o av n squared.

94
00:05:26,690 --> 00:05:30,560
Du kan velge boble sortere, valg
sorter eller innsetting sortere, eller

95
00:05:30,560 --> 00:05:32,670
noen annen form vi ikke har
sett i klassen.

96
00:05:32,670 --> 00:05:36,380
Men her skal vi
bruke valget slag.

97
00:05:36,380 --> 00:05:40,030
>> Så vi kommer til å reagere
over hele matrisen.

98
00:05:40,030 --> 00:05:44,360
Vel, her ser vi at vi gjentar
fra 0 til n minus en.

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

100
00:05:45,990 --> 00:05:49,320
Vel, hvis vi allerede har sortert den første
n minus 1 elementer, deretter den

101
00:05:49,320 --> 00:05:54,420
aller siste element hva må allerede være
på riktig sted, slik at sortering løpet

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

103
00:05:56,520 --> 00:05:58,770
>> Nå husker hvordan valg
Sorter fungerer.

104
00:05:58,770 --> 00:06:01,950
Vi kommer til å gå over hele matrisen
ser for minimumsverdien i

105
00:06:01,950 --> 00:06:04,480
matrisen og pinne som
i begynnelsen.

106
00:06:04,480 --> 00:06:07,610
Så får vi kommer til å gå over hele
matrise igjen på jakt etter den andre

107
00:06:07,610 --> 00:06:10,410
minste element, og pinne som
i den andre stilling i

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

109
00:06:12,100 --> 00:06:14,330
Så, det er hva dette gjør.

110
00:06:14,330 --> 00:06:17,290
>> Her ser vi at vi er
sette gjeldende minste

111
00:06:17,290 --> 00:06:20,030
Verdien til den i-te indeks.

112
00:06:20,030 --> 00:06:23,160
Så på den første iterasjon, skal vi
å vurdere minimumsverdien til å være

113
00:06:23,160 --> 00:06:25,030
starten av våre array.

114
00:06:25,030 --> 00:06:28,500
Deretter kommer vi til å iterere over
Resten av matrisen, å kontrollere

115
00:06:28,500 --> 00:06:31,870
se om det ikke noe element som er mindre enn
den som vi er nå

116
00:06:31,870 --> 00:06:33,900
med tanke på minimum.

117
00:06:33,900 --> 00:06:38,840
>> Så her, verdier j pluss én - det er
mindre enn hva vi er i dag

118
00:06:38,840 --> 00:06:40,380
med tanke på minimum.

119
00:06:40,380 --> 00:06:42,940
Så skal vi oppdatere hva
vi tror er minimum for å

120
00:06:42,940 --> 00:06:44,640
indeksen j pluss en.

121
00:06:44,640 --> 00:06:48,540
Så, gjør det over hele matrisen,
og etter denne for sløyfen, minimum

122
00:06:48,540 --> 00:06:53,160
bør være minimum elementet fra
i-te posisjonen i matrisen.

123
00:06:53,160 --> 00:06:57,350
>> Når vi har det, kan vi bytte
minimumsverdi inn i i-te posisjon

124
00:06:57,350 --> 00:06:58,230
i matrisen.

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

126
00:07:00,130 --> 00:07:03,940
Vi lagrer i en midlertidig verdi -
i-te verdien i matrisen -

127
00:07:03,940 --> 00:07:08,460
satt inn i den i-te verdi i matrisen i
minimumsverdi som hører til der,

128
00:07:08,460 --> 00:07:13,580
og deretter lagre tilbake til der
værende minimumsverdi som brukes for å være den

129
00:07:13,580 --> 00:07:16,460
i-te verdi i matrisen, slik at
at vi ikke mister det.

130
00:07:16,460 --> 00:07:20,510
>> Så, som fortsetter på
neste iterasjon.

131
00:07:20,510 --> 00:07:23,480
Vi vil begynne å lete etter den andre
minimumsverdi, og sett det inn i

132
00:07:23,480 --> 00:07:24,590
andre stilling.

133
00:07:24,590 --> 00:07:27,440
På den tredje iterasjon, vil vi se etter
den tredje minimumsverdi og innsats

134
00:07:27,440 --> 00:07:31,550
at i den tredje posisjonen, og så
på før vi har en sortert array.

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

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