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

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

3
00:00:15,010 --> 00:00:16,790
Miten käytämme binäärihaku?

4
00:00:16,790 --> 00:00:18,770
Otetaan selvää.

5
00:00:18,770 --> 00:00:23,400
Niin, huomaa, että tämä haku aiomme
toteuttaa rekursiivisesti.

6
00:00:23,400 --> 00:00:27,470
Voisit myös toteuttaa binäärihaku
iteratiivisesti, joten jos teit sen,

7
00:00:27,470 --> 00:00:29,280
se on täysin kunnossa.

8
00:00:29,280 --> 00:00:32,820
>> Nyt ensimmäinen, muistakaamme, mitä
parametreja haku on tarkoitus olla.

9
00:00:32,820 --> 00:00:36,120
Tässä näemme int-arvo, joka on
tarkoitus olla arvoa käyttäjä on

10
00:00:36,120 --> 00:00:37,320
etsivät.

11
00:00:37,320 --> 00:00:40,800
Näemme int arvot array, joka
on joukko, jossa olemme

12
00:00:40,800 --> 00:00:42,520
etsivät arvon.

13
00:00:42,520 --> 00:00:45,602
Ja me näemme int n, joka on
pituus meidän array.

14
00:00:45,602 --> 00:00:47,410
>> Nyt ensimmäinen asia ensin.

15
00:00:47,410 --> 00:00:51,350
Tarkistamme jos n = 0, in
jolloin palaamme vääriä.

16
00:00:51,350 --> 00:00:54,770
Se vain sanoo, jos meillä on tyhjä
array, arvo ei selvästikään ole

17
00:00:54,770 --> 00:00:57,860
tyhjä jono, jotta voimme palauttaa false.

18
00:00:57,860 --> 00:01:01,250
>> Nyt me todella haluamme tehdä binary
search osa binäärihaku.

19
00:01:01,250 --> 00:01:04,780
Joten, haluamme löytää keskellä
osa tätä array.

20
00:01:04,780 --> 00:01:09,130
Täällä sanomme keskellä yhtä kuin n jaettu
2, koska keskimmäinen osa on

21
00:01:09,130 --> 00:01:12,240
olemaan pituus
meidän array jaettuna 2.

22
00:01:12,240 --> 00:01:15,040
Nyt aiomme tarkistaa, onko
keskielementti vastaa arvoa olemme

23
00:01:15,040 --> 00:01:16,160
etsivät.

24
00:01:16,160 --> 00:01:21,030
Joten jos arvot keskimmäinen vastaa arvoa, me
voi palata paikkansa, sillä löysimme

25
00:01:21,030 --> 00:01:22,810
arvo meidän array.

26
00:01:22,810 --> 00:01:26,380
>> Mutta jos se ei ollut totta, nyt
meidän täytyy tehdä rekursiivinen

27
00:01:26,380 --> 00:01:27,840
vaiheen binäärihaku.

28
00:01:27,840 --> 00:01:30,450
Meidän täytyy etsiä joko
jäljellä array tai

29
00:01:30,450 --> 00:01:32,320
keskellä jono.

30
00:01:32,320 --> 00:01:39,280
Joten tässä, sanomme jos arvot keskellä on
pienempi kuin arvo, se tarkoittaa, että arvo

31
00:01:39,280 --> 00:01:41,350
oli suurempi kuin keski-
jono.

32
00:01:41,350 --> 00:01:45,790
Joten arvon on oltava oikealla puolella
elementti, että me vain katsoi.

33
00:01:45,790 --> 00:01:48,090
>> Joten tässä, me aiomme
etsi rekursiivisesti.

34
00:01:48,090 --> 00:01:50,320
Ja me tarkastelemme mitä olemme ohimennen
Tämän toisessa.

35
00:01:50,320 --> 00:01:53,440
Mutta aiomme hakevat
oikealla keskellä elementin.

36
00:01:53,440 --> 00:01:57,710
Ja toisessa tapauksessa, se tarkoittaa, että
-arvo oli pienempi kuin keskellä

37
00:01:57,710 --> 00:02:00,660
jono, ja niin aiomme
etsiä vasemmalle.

38
00:02:00,660 --> 00:02:03,520
Nyt, vasen tulee olemaan
hieman helpompi katsoa.

39
00:02:03,520 --> 00:02:07,770
Niin, tässä näemme, että olemme rekursiivisesti
soittamalla Missä ensin

40
00:02:07,770 --> 00:02:10,120
argumentti on, jälleen, arvo
Etsimme yli.

41
00:02:10,120 --> 00:02:14,970
Toinen argumentti tulee olemaan
array että olimme etsivät yli.

42
00:02:14,970 --> 00:02:17,090
Ja viimeinen osa on nyt keskellä.

43
00:02:17,090 --> 00:02:21,650
Muista viimeinen parametri on meidän int
n, niin se pituus meidän array.

44
00:02:21,650 --> 00:02:25,310
>> Vuonna rekursiivinen kutsu etsiä, olemme
sanovat nyt, että pituus

45
00:02:25,310 --> 00:02:27,230
array on keskellä.

46
00:02:27,230 --> 00:02:32,900
Joten, jos meidän joukko oli koko 20 ja me
etsinyt indeksissä 10, koska keskellä on

47
00:02:32,900 --> 00:02:36,930
20 jaettuna 2, se tarkoittaa, että olemme
läpäisivät 10 uudeksi

48
00:02:36,930 --> 00:02:38,300
pituus meidän array.

49
00:02:38,300 --> 00:02:41,910
Muista, että kun sinulla on array
pituuden 10, se tarkoittaa voimassa

50
00:02:41,910 --> 00:02:45,450
elementit ovat indeksejä 0 kautta 9.

51
00:02:45,450 --> 00:02:50,120
Joten tämä on juuri sitä, mitä haluamme
tarkensimme päivitetty array - vasen

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

53
00:02:53,010 --> 00:02:55,710
>> Joten, etsii oikealla on
hieman vaikeaa.

54
00:02:55,710 --> 00:03:00,170
Nyt ensimmäinen Tarkastellaan pituus
array oikealle

55
00:03:00,170 --> 00:03:01,240
keskielementti.

56
00:03:01,240 --> 00:03:08,390
Joten, jos meidän joukko oli koko n jälkeen
new Array tulee olemaan kooltaan n miinus

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

58
00:03:10,140 --> 00:03:12,530
Joten, nyt ajatella n miinus keskellä.

59
00:03:12,530 --> 00:03:18,710
>> Jälleen, jos joukko olivat kooltaan 20 ja
jaamme 2 saada keskelle,

60
00:03:18,710 --> 00:03:23,540
niin keskellä on 10, niin n miinus keskellä
aikoo antaa meille 10, joten 10

61
00:03:23,540 --> 00:03:25,330
elementtejä oikealla keskellä.

62
00:03:25,330 --> 00:03:27,780
Mutta meillä on myös tämä miinus
1, koska emme halua

63
00:03:27,780 --> 00:03:29,700
kuuluu keskellä itse.

64
00:03:29,700 --> 00:03:34,190
Joten n miinus keskellä miinus 1 antaa meille
kokonaismäärä elementtejä oikea

65
00:03:34,190 --> 00:03:36,800
Keskimmäisen indeksin array.

66
00:03:36,800 --> 00:03:41,870
>> Nyt täällä, muista, että keskimmäinen
parametri on arvojen jono.

67
00:03:41,870 --> 00:03:46,180
Joten tässä, jossa olemme
päivitetyt arvot array.

68
00:03:46,180 --> 00:03:50,930
Tämä arvoja plus keskellä plus 1 on
todella sanovat rekursiivisesti soittaa

69
00:03:50,930 --> 00:03:56,460
haku, ohimennen new Array, jossa
että uudet array alkaa keskellä

70
00:03:56,460 --> 00:03:59,370
plus yksi alkuperäiset arvot array.

71
00:03:59,370 --> 00:04:05,400
>> Vaihtoehtoinen syntaksi, että nyt
olet alkanut nähdä viitteitä, on

72
00:04:05,400 --> 00:04:10,170
Et-arvojen keskellä plus 1.

73
00:04:10,170 --> 00:04:17,149
Joten, tartu osoite keskellä
plus yksi osa arvoista.

74
00:04:17,149 --> 00:04:23,690
>> Nyt, jos et olisi mukava
muuttamalla array kuin, että voit

75
00:04:23,690 --> 00:04:28,900
olisi myös voinut toteuttaa tämän käyttämällä
rekursiivinen auttaja-toiminto, jossa

76
00:04:28,900 --> 00:04:31,680
että auttaja toiminto vie
lisää argumentteja.

77
00:04:31,680 --> 00:04:36,610
Joten sen sijaan että vain arvo,
array, ja taulukon koko,

78
00:04:36,610 --> 00:04:42,315
auttajafunktio voisi ottaa enemmän
argumentteja, mukaan lukien alaindeksi

79
00:04:42,315 --> 00:04:45,280
että olisit välitä jono
ja ylempi indeksi että välität

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

81
00:04:46,300 --> 00:04:49,770
>> Ja niin pitää kirjaa sekä alemman
indeksi ja ylempi indeksi, et

82
00:04:49,770 --> 00:04:52,780
tarvitse koskaan muuttaa
alkuperäiset arvot array.

83
00:04:52,780 --> 00:04:56,390
Voit vain jatkaa
käyttää arvoja array.

84
00:04:56,390 --> 00:04:59,540
Mutta täällä, huomaa emme tarvitse auttaja
toimivat niin kauan kuin olemme

85
00:04:59,540 --> 00:05:01,760
halukas muuttamaan alkuperäistä
arvot array.

86
00:05:01,760 --> 00:05:05,020
Olemme valmiita kulkemaan
päivitetyt arvot.

87
00:05:05,020 --> 00:05:09,140
>> Nyt emme voi binäärihaku yli
array, joka on lajittelemattoman.

88
00:05:09,140 --> 00:05:12,220
Joten, hoidetaan homma kuntoon.

89
00:05:12,220 --> 00:05:17,650
Nyt, huomaa, että sellainen on viimeisen kahden
parametrit int arvot, jotka on

90
00:05:17,650 --> 00:05:21,110
array että olemme lajittelu, int n,
joka on pituus array, joka

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

92
00:05:22,250 --> 00:05:24,840
Niin, tässä haluamme toteuttaa
Lajittelualgoritmi

93
00:05:24,840 --> 00:05:26,690
, joka on O n potenssiin.

94
00:05:26,690 --> 00:05:30,560
Voisit valita kupla lajitella, valinta
lajittele tai lisäyslajittelu tai

95
00:05:30,560 --> 00:05:32,670
muu sellainen meillä ole
nähnyt luokassa.

96
00:05:32,670 --> 00:05:36,380
Mutta täällä, me aiomme
Käytä valinta lajitella.

97
00:05:36,380 --> 00:05:40,030
>> Joten, aiomme kerrata
koko ryhmän yli.

98
00:05:40,030 --> 00:05:44,360
No, tässä näemme, että olemme iteroimalla
0-n miinus 1.

99
00:05:44,360 --> 00:05:45,990
Miksi ei kaikki tavalla jopa n?

100
00:05:45,990 --> 00:05:49,320
No, jos olemme jo järjestetty ensimmäinen
n miinus 1 elementit, sitten

101
00:05:49,320 --> 00:05:54,420
Aivan viimeinen elementti, mitä on jo oltava
oikeassa paikassa, joten lajittelu yli

102
00:05:54,420 --> 00:05:56,520
koko ryhmän.

103
00:05:56,520 --> 00:05:58,770
>> Nyt muistan miten valinta
lajitella toimii.

104
00:05:58,770 --> 00:06:01,950
Aiomme mennä koko ryhmän yli
etsii pienimmän arvon

105
00:06:01,950 --> 00:06:04,480
array ja keppiä että
alussa.

106
00:06:04,480 --> 00:06:07,610
Sitten aiomme mennä yli koko
array taas etsii toista

107
00:06:07,610 --> 00:06:10,410
pienin alkio, ja keppi
toisessa asemassa

108
00:06:10,410 --> 00:06:12,100
jono, ja niin edelleen.

109
00:06:12,100 --> 00:06:14,330
Niin, sitähän tämä on tekemässä.

110
00:06:14,330 --> 00:06:17,290
>> Täällä, me näemme, että olemme
asetetaan nykyinen minimi

111
00:06:17,290 --> 00:06:20,030
arvo i: nnen indeksin.

112
00:06:20,030 --> 00:06:23,160
Joten ensimmäistä iterointia, aiomme
harkitsemaan pienin arvo on

113
00:06:23,160 --> 00:06:25,030
alussa meidän array.

114
00:06:25,030 --> 00:06:28,500
Sitten aiomme kerrata yli
Loput array, tarkkailun

115
00:06:28,500 --> 00:06:31,870
onko olemassa mitään osia pienempi kuin
yksi että olemme tällä hetkellä

116
00:06:31,870 --> 00:06:33,900
huomioon minimiin.

117
00:06:33,900 --> 00:06:38,840
>> Joten tässä, arvot j plus yksi - se on
vähemmän kuin mitä meillä tällä hetkellä

118
00:06:38,840 --> 00:06:40,380
huomioon minimiin.

119
00:06:40,380 --> 00:06:42,940
Sitten aiomme päivittää mitä
mielestämme on minimi

120
00:06:42,940 --> 00:06:44,640
Hakemisto J plus 1.

121
00:06:44,640 --> 00:06:48,540
Joten, että koko jono,
ja tämän jälkeen silmukka, minimi

122
00:06:48,540 --> 00:06:53,160
pitäisi olla vähintään elementin
i: nnen aseman jono.

123
00:06:53,160 --> 00:06:57,350
>> Kun meillä on tuo, voimme vaihtaa
minimiarvo osaksi i. asema

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

125
00:06:58,230 --> 00:07:00,130
Joten tämä on vain standardi swap.

126
00:07:00,130 --> 00:07:03,940
Tallennamme väliaikaiseen arvo -
i: nnen arvon array -

127
00:07:03,940 --> 00:07:08,460
otetaan i: nnen arvon array
pienin arvo, joka kuuluu sinne,

128
00:07:08,460 --> 00:07:13,580
ja sitten tallentaa takaisin, jos
nykyinen minimiarvo käytetään olla

129
00:07:13,580 --> 00:07:16,460
i: nnen arvon jono, niin
että emme menetä sitä.

130
00:07:16,460 --> 00:07:20,510
>> Niin, että jatkuu
seuraavaan toistoon.

131
00:07:20,510 --> 00:07:23,480
Aloitamme etsii toista
minimiarvo ja aseta sen osaksi

132
00:07:23,480 --> 00:07:24,590
toiseen asentoon.

133
00:07:24,590 --> 00:07:27,440
Kolmantena iteraatio, me etsiä
kolmannen minimiarvo ja insertti

134
00:07:27,440 --> 00:07:31,550
että kolmanteen asentoon, ja niin
kunnes olemme lajitellun array.

135
00:07:31,550 --> 00:07:33,820
Nimeni on Rob, ja tämä
oli valinta lajitella.

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