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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Tere, ma olen Rob.

3
00:00:15,010 --> 00:00:16,790
Kuidas me tööle binaarne otsing?

4
00:00:16,790 --> 00:00:18,770
Uurime välja.

5
00:00:18,770 --> 00:00:23,400
Seega pidage meeles, et see otsing me
rakendada rekursiivselt.

6
00:00:23,400 --> 00:00:27,470
Sa võid ka ellu binaarne otsing
korduvalt, nii et kui sa seda tegid,

7
00:00:27,470 --> 00:00:29,280
see on täiesti trahvi.

8
00:00:29,280 --> 00:00:32,820
>> Nüüd esimene, pidagem meeles, mida
parameetrid otsing on mõeldud.

9
00:00:32,820 --> 00:00:36,120
Siin näeme, int väärtust, mis on
peaks olema väärtus on kasutaja

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

11
00:00:37,320 --> 00:00:40,800
Näeme int väärtusi massiivi, mis
on massiiv, kus me oleme

12
00:00:40,800 --> 00:00:42,520
otsivad raha.

13
00:00:42,520 --> 00:00:45,602
Ja me näeme, int n, mis on
pikkus meie massiivi.

14
00:00:45,602 --> 00:00:47,410
>> Nüüd esimene asi esimesena.

15
00:00:47,410 --> 00:00:51,350
Me vaadata, kui n on 0, on
mille puhul me tagasi false.

16
00:00:51,350 --> 00:00:54,770
See on lihtsalt öeldes, kui meil on tühi
massiiv, väärtus ei ole kindlasti

17
00:00:54,770 --> 00:00:57,860
tühi massiiv, nii et me saame tagasi false.

18
00:00:57,860 --> 00:01:01,250
>> Nüüd, kui me tegelikult tahame teha binaarne
search osa binaarne otsing.

19
00:01:01,250 --> 00:01:04,780
Niisiis, me tahame leida kuldset
element selle massiivi.

20
00:01:04,780 --> 00:01:09,130
Siin me ütleme, keskel on n jagatud
2, kuna keset element

21
00:01:09,130 --> 00:01:12,240
saab olema pikkuse
meie array jagatud 2.

22
00:01:12,240 --> 00:01:15,040
Nüüd me ei kavatse vaadata, kui
keskel element võrdub raha oleme

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

24
00:01:16,160 --> 00:01:21,030
Nii et kui väärtuste keskel võrdne väärtus, me
võib naasta tõsi, sest me leidsime

25
00:01:21,030 --> 00:01:22,810
väärtus meie massiivi.

26
00:01:22,810 --> 00:01:26,380
>> Aga kui see ei ole tõsi, nüüd
meil on vaja teha rekursiivne

27
00:01:26,380 --> 00:01:27,840
samm binaarne otsing.

28
00:01:27,840 --> 00:01:30,450
Meil on vaja otsida kas
vasakule massiivi või

29
00:01:30,450 --> 00:01:32,320
keset massiiv.

30
00:01:32,320 --> 00:01:39,280
Nii et siin me ütleme, kui väärtuste keskel on
väiksem väärtus, see tähendab, et väärtus

31
00:01:39,280 --> 00:01:41,350
oli suurem kui keskel
massiivi.

32
00:01:41,350 --> 00:01:45,790
Seega väärtus peab olema õigus
element, mida me lihtsalt vaatasin.

33
00:01:45,790 --> 00:01:48,090
>> Nii et siin me läheme
otsi rekursiivselt.

34
00:01:48,090 --> 00:01:50,320
Ja me vaatame, mida me läbiva
seda võetakse teine.

35
00:01:50,320 --> 00:01:53,440
Aga me kontrollime,
õigus keset element.

36
00:01:53,440 --> 00:01:57,710
Ja teisel juhul tähendab see, et
väärtus oli alla keskele

37
00:01:57,710 --> 00:02:00,660
massiiv, ja nii me
otsida üles vasakule.

38
00:02:00,660 --> 00:02:03,520
Nüüd vasakule saab olema
natuke lihtsam vaadata.

39
00:02:03,520 --> 00:02:07,770
Niisiis, me näeme siin, et me oleme rekursiivselt
kutsudes otsing kui esimene

40
00:02:07,770 --> 00:02:10,120
argument on jälle väärtus
me otsime üle.

41
00:02:10,120 --> 00:02:14,970
Teine argument saab olema
massiivi otsiti läbi.

42
00:02:14,970 --> 00:02:17,090
Ja viimane element on nüüd keskel.

43
00:02:17,090 --> 00:02:21,650
Mäleta viimane parameeter on meie int
n, nii et see pikkus meie massiivi.

44
00:02:21,650 --> 00:02:25,310
>> In rekursiivne kõne otsida, me oleme
nüüd selge, et pikkus

45
00:02:25,310 --> 00:02:27,230
massiiv on keskel.

46
00:02:27,230 --> 00:02:32,900
Niisiis, kui meie array oli suurus 20 ja me
otsitakse indeksiga 10, sest keskel on

47
00:02:32,900 --> 00:02:36,930
20 jagatud 2, see tähendab, et me oleme
möödaminnes 10 nagu uus

48
00:02:36,930 --> 00:02:38,300
pikkus meie massiivi.

49
00:02:38,300 --> 00:02:41,910
Pea meeles, et kui sul on array
pikkusega 10, mis tähendab, et kehtivad

50
00:02:41,910 --> 00:02:45,450
elemendid on indeksid 0 kuni 9.

51
00:02:45,450 --> 00:02:50,120
Nii et see on täpselt see, mida me tahame
täpsustada meie uuendatud array - vasak

52
00:02:50,120 --> 00:02:53,010
array keskelt element.

53
00:02:53,010 --> 00:02:55,710
>> Niisiis, otsin õige on
natuke raskem.

54
00:02:55,710 --> 00:03:00,170
Nüüd esimene Vaatleme pikkus
massiivi paremal

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

56
00:03:01,240 --> 00:03:08,390
Niisiis, kui meie massiivi oli suurus n siis
uus massiiv suurusega n miinus

57
00:03:08,390 --> 00:03:10,140
keskel miinus 1.

58
00:03:10,140 --> 00:03:12,530
Niisiis, oletame, mõtlema n miinus keskel.

59
00:03:12,530 --> 00:03:18,710
>> Jällegi, kui massiivi olid suurusega 20 ja
me jagame 2 saada keskel

60
00:03:18,710 --> 00:03:23,540
nii keskel on 10, siis n miinus keskel
läheb meile 10, nii et 10

61
00:03:23,540 --> 00:03:25,330
elemente paremal keskel.

62
00:03:25,330 --> 00:03:27,780
Aga meil on ka see miinus
1, sest me ei taha

63
00:03:27,780 --> 00:03:29,700
sisaldama keskel ise.

64
00:03:29,700 --> 00:03:34,190
Nii n miinus keskel miinus 1 annab meile
koguarv elemente paremal

65
00:03:34,190 --> 00:03:36,800
Keskmise index massiiv.

66
00:03:36,800 --> 00:03:41,870
>> Nüüd, pea meeles, et keskmine
parameeter on väärtuste massiivi.

67
00:03:41,870 --> 00:03:46,180
Nii et siin me oleme kulgeb
uuendatud väärtuste massiivi.

68
00:03:46,180 --> 00:03:50,930
See väärtused pluss keskel pluss 1 on
tegelikult öelda rekursiivselt helistada

69
00:03:50,930 --> 00:03:56,460
otsing, mis kulgeb uus massiiv, kus
et uus massiiv hakkab keset

70
00:03:56,460 --> 00:03:59,370
pluss üks meie algseaded massiivi.

71
00:03:59,370 --> 00:04:05,400
>> Asendusliikme süntaks, et nüüd,
olete hakanud näha suunanäitajaks, on

72
00:04:05,400 --> 00:04:10,170
ampersand väärtuste keskel pluss 1.

73
00:04:10,170 --> 00:04:17,149
Niisiis, ostke aadress keskel
pluss üks element väärtused.

74
00:04:17,149 --> 00:04:23,690
>> Nüüd, kui te ei ole mugav
muuta massiivi niimoodi, siis

75
00:04:23,690 --> 00:04:28,900
oleks ka rakendanud kasutades
rekursiivne abistaja funktsiooni, kus

76
00:04:28,900 --> 00:04:31,680
et abistaja funktsiooni võtab
rohkem argumente.

77
00:04:31,680 --> 00:04:36,610
Seega selle asemel, et lihtsalt raha,
massiivi ning suurust massiivi

78
00:04:36,610 --> 00:04:42,315
abistaja funktsiooni võiks rohkem
argumente, sealhulgas alaindeksi

79
00:04:42,315 --> 00:04:45,280
et teil oleks hooli massiivi
ja ülemine register, et sa hoolid

80
00:04:45,280 --> 00:04:46,300
umbes massiiv.

81
00:04:46,300 --> 00:04:49,770
>> Ja jälgida nii madalam
indeks ja ülemine register, sa ei pea

82
00:04:49,770 --> 00:04:52,780
pea kunagi muutma
Algsete massiivi.

83
00:04:52,780 --> 00:04:56,390
Sa võid jätkata
kasuta väärtuste massiivi.

84
00:04:56,390 --> 00:04:59,540
Aga siin, teate, me ei pea abimees
toimida nii kaua kui me oleme

85
00:04:59,540 --> 00:05:01,760
valmis muuta esialgse
väärtuste massiivi.

86
00:05:01,760 --> 00:05:05,020
Oleme valmis läbima
ajakohastatud väärtusi.

87
00:05:05,020 --> 00:05:09,140
>> Nüüd ei saa me Kahendotsingupuu üle
massiivi sortimata.

88
00:05:09,140 --> 00:05:12,220
Nii, lähme seda lahendada.

89
00:05:12,220 --> 00:05:17,650
Nüüd märkate, et sort on viimase kahe
parameetrite int väärtusi, mis on

90
00:05:17,650 --> 00:05:21,110
massiivi pakin ja int n,
mis on pikkus massiivi

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

92
00:05:22,250 --> 00:05:24,840
Nii, siin me tahame ellu
sorteerimine algoritm

93
00:05:24,840 --> 00:05:26,690
mis o n ruudus.

94
00:05:26,690 --> 00:05:30,560
Sa võid valida mull sorteerida valik
sort või sisestamise sort, või

95
00:05:30,560 --> 00:05:32,670
mõne muu sort meil ei
näinud klassis.

96
00:05:32,670 --> 00:05:36,380
Aga siin me läheme
kasutage valikut sort.

97
00:05:36,380 --> 00:05:40,030
>> Niisiis, me kinnitada,
kogu massiiv.

98
00:05:40,030 --> 00:05:44,360
Noh, siin me näeme, et me iterating
0 kuni n miinus 1.

99
00:05:44,360 --> 00:05:45,990
Miks mitte kõik viis kuni n?

100
00:05:45,990 --> 00:05:49,320
Noh, kui me oleme juba valmis esimene
n miinus 1 elemente, siis

101
00:05:49,320 --> 00:05:54,420
väga viimane element, mida peab juba olema
õiges kohas, nii et sorteerimine üle

102
00:05:54,420 --> 00:05:56,520
kogu massiiv.

103
00:05:56,520 --> 00:05:58,770
>> Nüüd pidage meeles, kuidas valik
sort töötab.

104
00:05:58,770 --> 00:06:01,950
Me läheme üle kogu antennide massiivi
otsin minimaalse väärtuse

105
00:06:01,950 --> 00:06:04,480
massiivi ja kepp, mis
alguses.

106
00:06:04,480 --> 00:06:07,610
Siis me lähme kogu
array jälle otsin teise

107
00:06:07,610 --> 00:06:10,410
väikseim element ja kepp, mis
aasta teisel positsioonil

108
00:06:10,410 --> 00:06:12,100
massiiv, ja nii edasi.

109
00:06:12,100 --> 00:06:14,330
Nii see on, mida see teeb.

110
00:06:14,330 --> 00:06:17,290
>> Siin me näeme, et me oleme
millega praegune miinimum

111
00:06:17,290 --> 00:06:20,030
väärtust i-nda indeks.

112
00:06:20,030 --> 00:06:23,160
Nii esimese iteratsiooni, me
kaaluda minimaalne väärtus olla

113
00:06:23,160 --> 00:06:25,030
algus meie massiivi.

114
00:06:25,030 --> 00:06:28,500
Siis me Käi
ülejäänud massiiv, kontrollides, et

115
00:06:28,500 --> 00:06:31,870
vaata, kas on mingeid elemente väiksem
üks, et me oleme praegu

116
00:06:31,870 --> 00:06:33,900
arvestades minimaalne.

117
00:06:33,900 --> 00:06:38,840
>> Nii et siin, väärtustab j pluss üks - see on
vähem kui see, mida me praegu

118
00:06:38,840 --> 00:06:40,380
arvestades minimaalne.

119
00:06:40,380 --> 00:06:42,940
Siis me uuendada mida
me arvame, on minimaalne, et

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

121
00:06:44,640 --> 00:06:48,540
Niisiis, teha kogu massiiv,
ja pärast seda loop, minimaalne

122
00:06:48,540 --> 00:06:53,160
peaks olema minimaalne elemendi
i-nda positsiooni massiiv.

123
00:06:53,160 --> 00:06:57,350
>> Kui meil on, et me ei vaheta
minimaalse väärtuse i-nda positsiooni

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

125
00:06:58,230 --> 00:07:00,130
Nii et see on lihtsalt standard swap.

126
00:07:00,130 --> 00:07:03,940
Me salvestada ajutiselt väärtus -
i-nda väärtuse massiivi -

127
00:07:03,940 --> 00:07:08,460
pannakse i-nda väärtuse massiivi
minimaalne väärtus, mis kuulub sinna,

128
00:07:08,460 --> 00:07:13,580
ja siis hoidke tagasi, kui
praegune minimaalne väärtus varem

129
00:07:13,580 --> 00:07:16,460
i-nda väärtuse massiivi, nii
et me ei kaota.

130
00:07:16,460 --> 00:07:20,510
>> Nii, et jätkub
järgmise iteratsiooni.

131
00:07:20,510 --> 00:07:23,480
Hakkame otsima teist
minimaalne väärtus ning lisada, et arvesse

132
00:07:23,480 --> 00:07:24,590
teisel positsioonil.

133
00:07:24,590 --> 00:07:27,440
Kolmandal iteratsiooni, me otsima
Kolmanda minimaalne väärtus ning sisesta

134
00:07:27,440 --> 00:07:31,550
et kolmandasse asendisse ning
edasi, kuni meil on sorteeritud massiiv.

135
00:07:31,550 --> 00:07:33,820
Minu nimi on Rob ja see
oli valik sort.

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