1
00:00:00,000 --> 00:00:03,346
>> [Musiikkia]

2
00:00:03,346 --> 00:00:05,258

3
00:00:05,258 --> 00:00:06,220
>> DOUG Lloyd: Selvﾃ､.

4
00:00:06,220 --> 00:00:08,140
Joten binary haku on
algoritmi voimme kﾃ､yttﾃ､ﾃ､

5
00:00:08,140 --> 00:00:10,530
lﾃｶytﾃ､ﾃ､ elementin sisﾃ､llﾃ､ array.

6
00:00:10,530 --> 00:00:14,710
Toisin kuin lineaarinen haku, se vaatii
erityisedellytystﾃ､ tﾃ､ytyttﾃ､vﾃ､ etukﾃ､teen,

7
00:00:14,710 --> 00:00:19,020
mutta se on niin paljon tehokkaampaa, jos
tﾃ､mﾃ､ edellytys on, itse asiassa, tﾃ､yty.

8
00:00:19,020 --> 00:00:20,470
>> Niin mitﾃ､ idea tﾃ､ﾃ､llﾃ､?

9
00:00:20,470 --> 00:00:21,780
se on hajota ja hallitse.

10
00:00:21,780 --> 00:00:25,100
Haluamme pienentﾃ､ﾃ､
hakualuetta puoleen joka kerta

11
00:00:25,100 --> 00:00:27,240
jotta lﾃｶydettﾃ､isiin tavoite numero.

12
00:00:27,240 --> 00:00:29,520
Tﾃ､ssﾃ､ on, ettﾃ､ ehto
tulee pelata, vaikka.

13
00:00:29,520 --> 00:00:32,740
Voimme vain hyﾃｶdyntﾃ､ﾃ､ valtaa
poistamalla puolet elementit

14
00:00:32,740 --> 00:00:36,070
katsomatta edes
ne, jos jono on lajiteltu.

15
00:00:36,070 --> 00:00:39,200
>> Jos se on tﾃ､ydellinen sekoitus ylﾃｶs,
Emme voi vain kﾃ､sistﾃ､

16
00:00:39,200 --> 00:00:42,870
hﾃ､vitﾃ､ puolet elementtejﾃ､, koska
emme tiedﾃ､, mitﾃ､ me poisheittﾃ､minen.

17
00:00:42,870 --> 00:00:45,624
Mutta jos array lajitellaan,
Voimme tehdﾃ､ niin, koska me

18
00:00:45,624 --> 00:00:48,040
tietﾃ､vﾃ､t, ettﾃ､ kaiken
vasemmalle, missﾃ､ me tﾃ､llﾃ､ hetkellﾃ､ olemme

19
00:00:48,040 --> 00:00:50,500
on oltava pienempi kuin
arvo olemme tﾃ､llﾃ､ hetkellﾃ､.

20
00:00:50,500 --> 00:00:52,300
Ja kaiken
oikeus missﾃ､ olemme

21
00:00:52,300 --> 00:00:55,040
on oltava suurempi kuin arvo
me tarkastelee parhaillaan.

22
00:00:55,040 --> 00:00:58,710
>> Niin mitﾃ､ pseudokoodina
vaiheet binary haku?

23
00:00:58,710 --> 00:01:02,310
Toistamme tﾃ､tﾃ､, kunnes
array tai, kuten me kﾃ､ymme eteenpﾃ､in,

24
00:01:02,310 --> 00:01:07,740
sub paneelit pienempiﾃ､ paloja
alkuperﾃ､inen joukko, on koko 0.

25
00:01:07,740 --> 00:01:10,960
Laske puolivﾃ､li
Nykyisen osa array.

26
00:01:10,960 --> 00:01:14,460
>> Jos arvo etsit on
ettﾃ､ elementti array, lopeta.

27
00:01:14,460 --> 00:01:15,030
Lﾃｶysit sen.

28
00:01:15,030 --> 00:01:16,550
Sepﾃ､ hienoa.

29
00:01:16,550 --> 00:01:19,610
Muuten, jos tavoite on
vﾃ､hemmﾃ､n kuin mitﾃ､ keskellﾃ､,

30
00:01:19,610 --> 00:01:23,430
joten jos arvo etsimme
sillﾃ､ on alempi kuin mitﾃ､ nﾃ､emme,

31
00:01:23,430 --> 00:01:26,780
toista tﾃ､mﾃ､ prosessi uudelleen, mutta
muuttaa pﾃ､ﾃ､tepiste, vaan

32
00:01:26,780 --> 00:01:29,300
olemisen alkuperﾃ､isen
tﾃ､ydellinen tﾃ､yden valikoiman,

33
00:01:29,300 --> 00:01:34,110
olla vain vasemmalla
missﾃ､ me vain katsoi.

34
00:01:34,110 --> 00:01:38,940
>> Tiesimme, ettﾃ､ keskellﾃ､ oli liian korkea,
tai kohde oli alle keskellﾃ､,

35
00:01:38,940 --> 00:01:42,210
ja niin se on olemassa, jos se
olemassa lainkaan array,

36
00:01:42,210 --> 00:01:44,660
jonnekin vasemmalla keskipisteen.

37
00:01:44,660 --> 00:01:48,120
Ja niin me asettaa array
sijainti vain vasemmalla

38
00:01:48,120 --> 00:01:51,145
keskipisteen uudeksi pﾃ､ﾃ､tepiste.

39
00:01:51,145 --> 00:01:53,770
Sitﾃ､ vastoin, jos tavoite on
suurempi kuin mitﾃ､ keskellﾃ､,

40
00:01:53,770 --> 00:01:55,750
teemme tﾃ､smﾃ､lleen sama
prosessi, mutta sen sijaan me

41
00:01:55,750 --> 00:01:59,520
muuttaa aloituspisteen olla
juuri oikealla keskipisteen

42
00:01:59,520 --> 00:02:00,680
me vain lasketaan.

43
00:02:00,680 --> 00:02:03,220
Ja sitten, aloitamme uudelleen.

44
00:02:03,220 --> 00:02:05,220
>> Katsotaanpa visualisoida, OK?

45
00:02:05,220 --> 00:02:08,620
Joten siellﾃ､ on paljon menossa ja tﾃ､ﾃ､llﾃ､,
mutta tﾃ､ssﾃ､ on joukko 15 elementtejﾃ､.

46
00:02:08,620 --> 00:02:11,400
Ja aiomme olla pitﾃ､ﾃ､ kirjaa
paljon enemmﾃ､n juttuja tﾃ､llﾃ､ kertaa.

47
00:02:11,400 --> 00:02:13,870
Joten lineaarinen haku, olimme
vain vﾃ､littﾃ､minen kohde.

48
00:02:13,870 --> 00:02:15,869
Mutta tﾃ､llﾃ､ kertaa haluamme
vﾃ､litﾃ､ missﾃ､ olemme

49
00:02:15,869 --> 00:02:18,480
alkaa nﾃ､yttﾃ､ﾃ､, missﾃ､
pysﾃ､hdyimme etsimﾃ､ssﾃ､,

50
00:02:18,480 --> 00:02:21,876
ja mitﾃ､ keskipisteen
nykyisen taulukon.

51
00:02:21,876 --> 00:02:23,250
Joten tﾃ､ssﾃ､ sitﾃ､ mennﾃ､ﾃ､n binary haku.

52
00:02:23,250 --> 00:02:25,290
Olemme melko paljon hyvﾃ､ mennﾃ､, eikﾃｶ?

53
00:02:25,290 --> 00:02:28,650
Olen juuri menossa laittaa alas
Alla tﾃ､ﾃ､llﾃ､ joukko indeksejﾃ､.

54
00:02:28,650 --> 00:02:32,430
Tﾃ､mﾃ､ on pohjimmiltaan vain mitﾃ､ elementti
array puhumme.

55
00:02:32,430 --> 00:02:34,500
Lineaarinen haku, me
care, koska me

56
00:02:34,500 --> 00:02:36,800
tﾃ､ytyy tietﾃ､ﾃ､, kuinka monta
elementit olemme iteroimalla yli,

57
00:02:36,800 --> 00:02:40,010
mutta emme oikeastaan 窶銀€久ﾃ､litﾃ､ mitﾃ､
elementti me tarkastelee parhaillaan.

58
00:02:40,010 --> 00:02:41,014
Binary haku, teemme.

59
00:02:41,014 --> 00:02:42,930
Ja niin ne ovat vain
siellﾃ､ pieni opas.

60
00:02:42,930 --> 00:02:44,910
>> Jotta voimme aloittaa, eikﾃｶ?

61
00:02:44,910 --> 00:02:46,240
No, ei aivan.

62
00:02:46,240 --> 00:02:48,160
Muista mitﾃ､ sanoin
noin binary haku?

63
00:02:48,160 --> 00:02:50,955
Emme voi tehdﾃ､ sitﾃ､
lajittelemattomien array tai muuten,

64
00:02:50,955 --> 00:02:55,820
emme takaa, ettﾃ､
tiettyjﾃ､ osia tai arvot eivﾃ､t ole

65
00:02:55,820 --> 00:02:57,650
tahattomat
hﾃ､vittﾃ､ﾃ､ kun me vain

66
00:02:57,650 --> 00:02:59,920
pﾃ､ﾃ､ttﾃ､ﾃ､ ohittaa puolet jono.

67
00:02:59,920 --> 00:03:02,574
>> Astu siis yksi binary haku
on sinulla on lajiteltu array.

68
00:03:02,574 --> 00:03:05,240
Ja voit kﾃ､yttﾃ､ﾃ､ mitﾃ､ tahansa lajittelu
algoritmit olemme puhuneet

69
00:03:05,240 --> 00:03:06,700
saada sinut ettﾃ､ asentoon.

70
00:03:06,700 --> 00:03:10,370
Joten nyt olemme asemassa, jossa
voimme tehdﾃ､ binary haku.

71
00:03:10,370 --> 00:03:12,560
>> Joten toistaa prosessi
askel askeleelta ja pitﾃ､ﾃ､

72
00:03:12,560 --> 00:03:14,830
seurata, mitﾃ､ tapahtuu kun kuljemme.

73
00:03:14,830 --> 00:03:17,980
Joten ensimmﾃ､inen meidﾃ､n tﾃ､ytyy tehdﾃ､, on laskea
keskipiste nykyisen taulukon.

74
00:03:17,980 --> 00:03:20,620
No, me sanomme olemme, ensimmﾃ､inen
kaikki, etsii arvon 19.

75
00:03:20,620 --> 00:03:22,290
Yritﾃ､mme lﾃｶytﾃ､ﾃ､ numero 19.

76
00:03:22,290 --> 00:03:25,380
Ensimmﾃ､inen osa tﾃ､tﾃ､
array sijaitsee indeksi nolla,

77
00:03:25,380 --> 00:03:28,880
ja viimeinen osa tﾃ､tﾃ､
array sijaitsee olevan 14.

78
00:03:28,880 --> 00:03:31,430
Ja niin soitamme ne alun ja lopun.

79
00:03:31,430 --> 00:03:35,387
>> Joten laskemme keskipisteen
lisﾃ､ﾃ､mﾃ､llﾃ､ 0 plus 14 jaettuna 2;

80
00:03:35,387 --> 00:03:36,720
melko yksinkertainen keskipiste.

81
00:03:36,720 --> 00:03:40,190
Ja voimme sanoa, ettﾃ､
keskipiste on nyt 7.

82
00:03:40,190 --> 00:03:43,370
Joten on 15, mitﾃ､ etsimme?

83
00:03:43,370 --> 00:03:43,940
Ei se ei ole.

84
00:03:43,940 --> 00:03:45,270
Etsimme 19.

85
00:03:45,270 --> 00:03:49,400
Mutta me tiedﾃ､mme, ettﾃ､ 19 on suurempi
kuin mitﾃ､ lﾃｶysimme keskellﾃ､.

86
00:03:49,400 --> 00:03:52,470
>> Joten mitﾃ､ voimme tehdﾃ､ on
muuttaa aloituspiste

87
00:03:52,470 --> 00:03:57,280
olla juuri oikealla
keskipiste, ja toista prosessi uudestaan.

88
00:03:57,280 --> 00:04:01,690
Ja kun teemme sen, sanomme nyt
uusi alkupiste on array paikka 8.

89
00:04:01,690 --> 00:04:07,220
Mitﾃ､ olemme hoitaa tehokkaasti on
huomiotta kaikki vasemmalle 15.

90
00:04:07,220 --> 00:04:09,570
Olemme eliminoitu puoli
Ongelman, ja nyt,

91
00:04:09,570 --> 00:04:13,510
sen sijaan, etsiﾃ､
yli 15 elementtiﾃ､ meidﾃ､n array,

92
00:04:13,510 --> 00:04:15,610
meillﾃ､ on vain etsiﾃ､ yli 7.

93
00:04:15,610 --> 00:04:17,706
Joten 8 on uusi aloituspiste.

94
00:04:17,706 --> 00:04:19,600
14 on edelleen pﾃ､ﾃ､tepiste.

95
00:04:19,600 --> 00:04:21,430
>> Ja nyt, mennﾃ､ﾃ､n tﾃ､nﾃ､ uudelleen.

96
00:04:21,430 --> 00:04:22,810
Laskemme uusi keskipiste.

97
00:04:22,810 --> 00:04:27,130
8 plus 14 on 22, jaettuna 2 on 11.

98
00:04:27,130 --> 00:04:28,660
Tﾃ､tﾃ､kﾃｶ me etsimme?

99
00:04:28,660 --> 00:04:30,110
Ei se ei ole.

100
00:04:30,110 --> 00:04:32,930
Etsimme arvo, joka on
vﾃ､hemmﾃ､n kuin mitﾃ､ me juuri lﾃｶytﾃ､nyt.

101
00:04:32,930 --> 00:04:34,721
Joten aiomme toistaa
uudelleen.

102
00:04:34,721 --> 00:04:38,280
Aiomme muuttaa pﾃ､ﾃ､tepiste
olla vain vasemmalla keskipisteen.

103
00:04:38,280 --> 00:04:41,800
Joten uusi pﾃ､ﾃ､tepiste tulee 10.

104
00:04:41,800 --> 00:04:44,780
Ja nyt, se on vain osa
array olemme lajitella kautta.

105
00:04:44,780 --> 00:04:48,460
Joten olemme nyt poistettu
12 15 elementtiﾃ､.

106
00:04:48,460 --> 00:04:51,550
Tiedﾃ､mme, ettﾃ､ jos 19
olemassa jono, se

107
00:04:51,550 --> 00:04:57,210
on oltava olemassa jonnekin elementin
numero 8 ja elementin numero 10.

108
00:04:57,210 --> 00:04:59,400
>> Joten laskemme uuden keskipisteen uudelleen.

109
00:04:59,400 --> 00:05:02,900
8 + 10 on 18, jaettuna 2 on 9.

110
00:05:02,900 --> 00:05:05,074
Ja tﾃ､ssﾃ､ tapauksessa, katso,
tavoite on keskellﾃ､.

111
00:05:05,074 --> 00:05:06,740
Lﾃｶysimme juuri sitﾃ､, mitﾃ､ etsit.

112
00:05:06,740 --> 00:05:07,780
Voimme lopettaa.

113
00:05:07,780 --> 00:05:10,561
Olemme onnistuneesti
binﾃ､ﾃ､rihaku.

114
00:05:10,561 --> 00:05:11,060
Selvﾃ､.

115
00:05:11,060 --> 00:05:13,930
Joten me tiedﾃ､mme tﾃ､mﾃ､n algoritmi
toimii jos tavoite on

116
00:05:13,930 --> 00:05:16,070
jonnekin sisﾃ､llﾃ､ jono.

117
00:05:16,070 --> 00:05:19,060
Onko tﾃ､mﾃ､ algoritmi tyﾃｶ jos
tavoite ei ole array?

118
00:05:19,060 --> 00:05:20,810
No, aloitetaan se
uudelleen, ja tﾃ､llﾃ､ kertaa,

119
00:05:20,810 --> 00:05:23,380
Katsotaanpa elementille
16, joka visuaalisesti voimme nﾃ､hdﾃ､

120
00:05:23,380 --> 00:05:25,620
ei ole missﾃ､ﾃ､n pakassa.

121
00:05:25,620 --> 00:05:27,110
>> Alkupiste on jﾃ､lleen 0.

122
00:05:27,110 --> 00:05:28,590
Pﾃ､ﾃ､tepiste on jﾃ､lleen 14.

123
00:05:28,590 --> 00:05:32,490
Ne ovat indeksejﾃ､ ensimmﾃ､isen ja
viimeinen elementit tﾃ､ydellinen valikoima.

124
00:05:32,490 --> 00:05:36,057
Ja me mennﾃ､ lﾃ､pi me vain
meni lﾃ､pi uudelleen, yrittﾃ､ﾃ､ lﾃｶytﾃ､ﾃ､ 16,

125
00:05:36,057 --> 00:05:39,140
vaikka visuaalisesti, voimme jo
sanoa, ettﾃ､ se ei aio olla siellﾃ､.

126
00:05:39,140 --> 00:05:43,450
Haluamme vain varmistaa tﾃ､mﾃ､ algoritmi
tulee itse asiassa vielﾃ､ tyﾃｶtﾃ､ jollain tavalla

127
00:05:43,450 --> 00:05:46,310
ja ei jﾃ､tﾃ､ meitﾃ､
jumissa pﾃ､ﾃ､ttymﾃ､ttﾃｶmﾃ､ﾃ､n silmukkaan.

128
00:05:46,310 --> 00:05:48,190
>> Niin mitﾃ､ askel ensimmﾃ､inen?

129
00:05:48,190 --> 00:05:50,230
Laske puolivﾃ､li
nykyisen taulukon.

130
00:05:50,230 --> 00:05:52,790
Mikﾃ､ keskipisteen
Nykyisen array?

131
00:05:52,790 --> 00:05:54,410
No, se on 7, eikﾃｶ?

132
00:05:54,410 --> 00:05:57,560
14 plus 0 jaettuna 2 on 7.

133
00:05:57,560 --> 00:05:59,280
On 15, mitﾃ､ etsimme?

134
00:05:59,280 --> 00:05:59,780
Ei.

135
00:05:59,780 --> 00:06:02,930
Se on melko lﾃ､hellﾃ､, mutta etsimme
joiden arvo hieman suurempi kuin.

136
00:06:02,930 --> 00:06:06,310
>> Joten me tiedﾃ､mme, ettﾃ､ se tulee
olla missﾃ､ﾃ､n vasemmalle 15.

137
00:06:06,310 --> 00:06:08,540
Tavoitteena on suurempi kuin
mitﾃ､ on keskipiste.

138
00:06:08,540 --> 00:06:12,450
Ja niin asetamme uusia aloituspiste
olla juuri oikealla keskellﾃ､.

139
00:06:12,450 --> 00:06:16,130
Keskipiste on tﾃ､llﾃ､ hetkellﾃ､ 7, joten
sanokaamme uusi alkupiste on 8.

140
00:06:16,130 --> 00:06:18,130
Ja mitﾃ､ olemme tehokkaasti
tehdﾃ､ uudelleen ohitetaan

141
00:06:18,130 --> 00:06:21,150
koko vasen puoli jono.

142
00:06:21,150 --> 00:06:23,750
>> Nyt toistamme
kﾃ､sitellﾃ､ vielﾃ､ kerran.

143
00:06:23,750 --> 00:06:24,910
Laske uusi keskipiste.

144
00:06:24,910 --> 00:06:29,350
8 plus 14 on 22, jaettuna 2 on 11.

145
00:06:29,350 --> 00:06:31,060
On 23, mitﾃ､ etsimme?

146
00:06:31,060 --> 00:06:31,870
Valitettavasti ei.

147
00:06:31,870 --> 00:06:34,930
Etsimme arvo
joka on vﾃ､hemmﾃ､n kuin 23.

148
00:06:34,930 --> 00:06:37,850
Ja niin tﾃ､ssﾃ､ tapauksessa, menemme
muuttaa pﾃ､ﾃ､tepiste on vain

149
00:06:37,850 --> 00:06:40,035
vasemmalle nykyisen keskipisteen.

150
00:06:40,035 --> 00:06:43,440
Nykyinen keskipiste on 11, ja
niin me asettaa uusi pﾃ､ﾃ､tepiste

151
00:06:43,440 --> 00:06:46,980
Seuraavan kerran menemme
Tﾃ､mﾃ､n prosessin kautta 10.

152
00:06:46,980 --> 00:06:48,660
>> Jﾃ､lleen me mennﾃ､ lﾃ､pi uudelleen.

153
00:06:48,660 --> 00:06:49,640
Laske keskipiste.

154
00:06:49,640 --> 00:06:53,100
8 plus 10 jaettuna 2 on 9.

155
00:06:53,100 --> 00:06:54,750
On 19, mitﾃ､ etsimme?

156
00:06:54,750 --> 00:06:55,500
Valitettavasti ei.

157
00:06:55,500 --> 00:06:58,050
Olemme vielﾃ､ etsimﾃ､ssﾃ､
numero pienempi.

158
00:06:58,050 --> 00:07:02,060
Niin me muuttaa pﾃ､ﾃ､tepiste tﾃ､llﾃ､ kertaa
olla vain vasemmalla keskipisteen.

159
00:07:02,060 --> 00:07:05,532
Keskipiste on tﾃ､llﾃ､ hetkellﾃ､ 9,
joten pﾃ､ﾃ､tepiste on 8.

160
00:07:05,532 --> 00:07:07,920
Ja nyt, me vain etsimﾃ､ssﾃ､
yhdellﾃ､ alkiotaulukon.

161
00:07:07,920 --> 00:07:10,250
>> Mikﾃ､ keskipiste tﾃ､mﾃ､n array?

162
00:07:10,250 --> 00:07:13,459
No, se alkaa 8, se
pﾃ､ﾃ､ttyy 8, keskipiste on 8.

163
00:07:13,459 --> 00:07:14,750
Sitﾃ､kﾃｶ etsimme?

164
00:07:14,750 --> 00:07:16,339
Me etsimme 17?

165
00:07:16,339 --> 00:07:17,380
Ei, me etsimme 16.

166
00:07:17,380 --> 00:07:20,160
Joten jos se on olemassa joukko,
sen on olemassa jonnekin

167
00:07:20,160 --> 00:07:21,935
vasemmalle, missﾃ､ me nyt olemme.

168
00:07:21,935 --> 00:07:23,060
Joten mitﾃ､ me teemme?

169
00:07:23,060 --> 00:07:26,610
No, me asettaa pﾃ､ﾃ､tepiste on vain
vasemmalle nykyisen keskipisteen.

170
00:07:26,610 --> 00:07:29,055
Niin me muuttaa pﾃ､ﾃ､tepiste 7.

171
00:07:29,055 --> 00:07:32,120
Ymmﾃ､rrﾃ､tkﾃｶ, mitﾃ､ vain
tﾃ､ﾃ､llﾃ､ on tapahtunut, vaikka?

172
00:07:32,120 --> 00:07:33,370
Katso tﾃ､ﾃ､llﾃ､ nyt.

173
00:07:33,370 --> 00:07:35,970
>> Start on nyt suurempi kuin lopussa.

174
00:07:35,970 --> 00:07:39,620
Tehokkaasti, kaksi pﾃ､ﾃ､tﾃ､
meidﾃ､n array ovat ylittﾃ､neet,

175
00:07:39,620 --> 00:07:42,252
ja alkupiste on
nyt kun pﾃ､ﾃ､tepiste.

176
00:07:42,252 --> 00:07:43,960
No, joka ei
mitﾃ､ﾃ､n jﾃ､rkeﾃ､, eikﾃｶ?

177
00:07:43,960 --> 00:07:47,960
Joten nyt, mitﾃ､ voimme sanoa on meidﾃ､n
on osa joukko koko 0.

178
00:07:47,960 --> 00:07:50,110
Ja kun me mennyt
Tﾃ､ssﾃ､ vaiheessa voimme nyt

179
00:07:50,110 --> 00:07:53,940
taata, ettﾃ､ elementti 16
ei ole olemassa jono,

180
00:07:53,940 --> 00:07:56,280
koska alkupiste
ja pﾃ､ﾃ､tepiste ovat ristissﾃ､.

181
00:07:56,280 --> 00:07:58,340
Ja niin se ei ole siellﾃ､.

182
00:07:58,340 --> 00:08:01,340
Nyt, huomaa, ettﾃ､ tﾃ､mﾃ､ on hieman
eri kuin alkupiste ja loppu

183
00:08:01,340 --> 00:08:02,900
kohta on sama.

184
00:08:02,900 --> 00:08:05,030
Jos olisimme olleet etsimﾃ､ssﾃ､
17, se olisi

185
00:08:05,030 --> 00:08:08,870
ollut array, ja aloituspiste
ja loppupiste ettﾃ､ viime iterointia

186
00:08:08,870 --> 00:08:11,820
ennen nﾃ､itﾃ､ pistettﾃ､ ristissﾃ､,
olisimme lﾃｶytyi 17 siellﾃ､.

187
00:08:11,820 --> 00:08:15,510
Vasta kun he ylittﾃ､vﾃ､t ettﾃ､ voimme
taata, ettﾃ､ elementti ei

188
00:08:15,510 --> 00:08:17,180
olemassa jono.

189
00:08:17,180 --> 00:08:20,260
>> Joten vie paljon vﾃ､hemmﾃ､n
vaiheet kuin lineaarinen haku.

190
00:08:20,260 --> 00:08:23,250
Pahimmassa tapauksessa, meillﾃ､ oli
jakaa luettelon n alkion

191
00:08:23,250 --> 00:08:27,770
toistuvasti puolet lﾃｶytﾃ､ﾃ､ kohde,
joko siksi kohdistuselementti

192
00:08:27,770 --> 00:08:33,110
on jossain viimeisen
alueeseen tai sitﾃ､ ei ole lainkaan.

193
00:08:33,110 --> 00:08:37,830
Joten pahimmassa tapauksessa meidﾃ､n on
jakaa array-- tiedﾃ､t?

194
00:08:37,830 --> 00:08:40,510
Loki n kertaa; me
on leikata ongelma

195
00:08:40,510 --> 00:08:42,610
puolessa tietyn mﾃ､ﾃ､rﾃ､n kertoja.

196
00:08:42,610 --> 00:08:45,160
Ettﾃ､ monta kertaa on log n.

197
00:08:45,160 --> 00:08:46,510
>> Mikﾃ､ on parhaassa tapauksessa?

198
00:08:46,510 --> 00:08:48,899
No, ensimmﾃ､inen kerta
laskea keskipiste,

199
00:08:48,899 --> 00:08:50,190
lﾃｶydﾃ､mme mitﾃ､ etsimme.

200
00:08:50,190 --> 00:08:52,150
Kaikissa edellinen
esimerkkejﾃ､ binary haku

201
00:08:52,150 --> 00:08:55,489
Olemme juuri mennyt yli, jos meillﾃ､ olisi
etsinyt elementti 15,

202
00:08:55,489 --> 00:08:57,030
olisimme havainneet, ettﾃ､ heti.

203
00:08:57,030 --> 00:08:58,321
Se oli aivan alussa.

204
00:08:58,321 --> 00:09:01,200
Se oli keskipiste
ensimmﾃ､inen yritys split

205
00:09:01,200 --> 00:09:03,950
of jako binary haku.

206
00:09:03,950 --> 00:09:06,350
>> Ja niin pahimmassa
tapauksessa, binary haku toimii

207
00:09:06,350 --> 00:09:11,580
in log n, joka on olennaisesti parempi
kuin lineaarinen haku, pahimmassa tapauksessa.

208
00:09:11,580 --> 00:09:16,210
Parhaassa tapauksessa binary
haku toimii omega 1.

209
00:09:16,210 --> 00:09:18,990
Joten binary haku on paljon
parempi kuin lineaarinen haku,

210
00:09:18,990 --> 00:09:23,270
mutta sinun tﾃ､ytyy kﾃ､sitellﾃ､ prosessi
lajittelu array ennen kuin voit

211
00:09:23,270 --> 00:09:26,140
hyﾃｶdyntﾃ､ﾃ､ valtaa binﾃ､ﾃ､rihaku.

212
00:09:26,140 --> 00:09:27,130
>> Olen Doug Lloyd.

213
00:09:27,130 --> 00:09:29,470
Tﾃ､mﾃ､ on CS 50.

214
00:09:29,470 --> 00:09:31,070