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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Ahoj, ja som Rob.

3
00:00:15,010 --> 00:00:16,790
Ako používame binárne hľadanie?

4
00:00:16,790 --> 00:00:18,770
Poďme zistiť.

5
00:00:18,770 --> 00:00:23,400
Takže, na vedomie, že toto hľadanie ideme
vykonávať rekurzívne.

6
00:00:23,400 --> 00:00:27,470
Dalo by sa tiež vykonávať binárne vyhľadávanie
iteratívne, takže ak to urobíte,

7
00:00:27,470 --> 00:00:29,280
To je úplne v poriadku.

8
00:00:29,280 --> 00:00:32,820
>> Teraz prvýkrát, poďme si spomenúť, čo
Parametre pre hľadanie majú byť.

9
00:00:32,820 --> 00:00:36,120
Tu vidíme int hodnotu, ktorá je
má byť hodnota užívateľ

10
00:00:36,120 --> 00:00:37,320
vyhľadávanie.

11
00:00:37,320 --> 00:00:40,800
Vidíme pole int hodnoty, ktoré
je pole, v ktorom sme

12
00:00:40,800 --> 00:00:42,520
hľadá hodnotu.

13
00:00:42,520 --> 00:00:45,602
A vidíme, int n, čo je
dĺžka nášho poľa.

14
00:00:45,602 --> 00:00:47,410
>> Teraz, prvá vec, ktorú ako prvý.

15
00:00:47,410 --> 00:00:51,350
Skontrolujte sme sa zistiť, či n sa rovná 0, sa
takom prípade sa vrátime false.

16
00:00:51,350 --> 00:00:54,770
To len hovorím, ak máme prázdna
pole, hodnota je jednoznačne nie je

17
00:00:54,770 --> 00:00:57,860
prázdne pole, takže sa môžeme vrátiť false.

18
00:00:57,860 --> 00:01:01,250
>> Teraz sme vlastne chcete urobiť binárne
Vyhľadávanie súčasťou binárneho vyhľadávania.

19
00:01:01,250 --> 00:01:04,780
Takže, chceme nájsť stred
prvok tohto poľa.

20
00:01:04,780 --> 00:01:09,130
Tu hovoríme, stredné rovná n delí
o 2, pretože prostredný element je

21
00:01:09,130 --> 00:01:12,240
bude dĺžka
naše pole delené 2.

22
00:01:12,240 --> 00:01:15,040
Teraz budeme kontrolovať, či
prostredný element rovná hodnote stojíme

23
00:01:15,040 --> 00:01:16,160
vyhľadávanie.

24
00:01:16,160 --> 00:01:21,030
Takže ak hodnoty strednej rovná hodnote, sme
môže vrátiť true, pretože sme zistili, že

25
00:01:21,030 --> 00:01:22,810
hodnota v našom poli.

26
00:01:22,810 --> 00:01:26,380
>> Ale v prípade, že to nie je pravda, teraz
musíme urobiť rekurzívne

27
00:01:26,380 --> 00:01:27,840
krok binárne vyhľadávanie.

28
00:01:27,840 --> 00:01:30,450
Musíme hľadať buď
vľavo na pole alebo na

29
00:01:30,450 --> 00:01:32,320
uprostred poľa.

30
00:01:32,320 --> 00:01:39,280
Tak tu, môžeme povedať, že hodnoty na stred je
menšia ako hodnota, ktorá znamená, že hodnota

31
00:01:39,280 --> 00:01:41,350
bol väčší než uprostred
z poľa.

32
00:01:41,350 --> 00:01:45,790
Takže hodnota musí byť vpravo
prvok, ktorý sme práve pozrel na.

33
00:01:45,790 --> 00:01:48,090
>> Tak tu, ideme na
hľadať rekurzívne.

34
00:01:48,090 --> 00:01:50,320
A my sa pozrieme na to, čo sme okolo
k tomu v druhom.

35
00:01:50,320 --> 00:01:53,440
Ale budeme hľadať na
vpravo od stredného prvku.

36
00:01:53,440 --> 00:01:57,710
A v druhom prípade, to znamená, že
hodnota bola nižšia ako uprostred

37
00:01:57,710 --> 00:02:00,660
pole, a tak ideme
hľadať na ľavej strane.

38
00:02:00,660 --> 00:02:03,520
Teraz, vľavo bude
trochu jednoduchšie pozrieť sa na.

39
00:02:03,520 --> 00:02:07,770
Takže, tu vidíme, že sme rekurzívne
volanie, kde prvý hľadanie

40
00:02:07,770 --> 00:02:10,120
argument je opäť hodnota
pozeráme cez.

41
00:02:10,120 --> 00:02:14,970
Druhý argument sa bude
pole, ktoré sme hľadali cez.

42
00:02:14,970 --> 00:02:17,090
A posledný prvok je teraz uprostred.

43
00:02:17,090 --> 00:02:21,650
Nezabudnite, posledný parameter je naša int
n, tak to je dĺžka nášho poľa.

44
00:02:21,650 --> 00:02:25,310
>> V rekurzívne volanie pre hľadanie, sme
Teraz hovorí, že dĺžka

45
00:02:25,310 --> 00:02:27,230
pole je stredná.

46
00:02:27,230 --> 00:02:32,900
Takže, ak naše pole bolo o veľkosti 20 a my
hľadal na index 10, pretože stred je

47
00:02:32,900 --> 00:02:36,930
20 deleno 2, to znamená, že sme
okolo 10 ako nový

48
00:02:36,930 --> 00:02:38,300
dĺžka nášho poľa.

49
00:02:38,300 --> 00:02:41,910
Pamätajte si, že keď máte pole
dĺžky 10, to znamená, že platí

50
00:02:41,910 --> 00:02:45,450
prvky sú v indexoch 0 až 9.

51
00:02:45,450 --> 00:02:50,120
Tak to je presne to, čo chceme
špecifikovať náš aktualizovaný poľa - ľavé

52
00:02:50,120 --> 00:02:53,010
poľa od stredu prvku.

53
00:02:53,010 --> 00:02:55,710
>> Takže, hľadá na pravej strane je
trochu zložitejšie.

54
00:02:55,710 --> 00:03:00,170
Teraz po prvýkrát, poďme zvážiť dĺžku
z poľa na pravej strane

55
00:03:00,170 --> 00:03:01,240
prostredný prvok.

56
00:03:01,240 --> 00:03:08,390
Takže, ak naše pole bolo veľkosti n, potom
Nová rada bude mať veľkosť n mínus

57
00:03:08,390 --> 00:03:10,140
stredná mínus 1.

58
00:03:10,140 --> 00:03:12,530
Takže, poďme si n mínus uprostred.

59
00:03:12,530 --> 00:03:18,710
>> Opäť platí, že v prípade, že pole bola veľkosti 20 a
delíme o 2 dostať stred,

60
00:03:18,710 --> 00:03:23,540
takže uprostred je 10, potom n mínus strednej
bude nám 10, takže 10

61
00:03:23,540 --> 00:03:25,330
prvky napravo od stredu.

62
00:03:25,330 --> 00:03:27,780
Ale máme tiež túto mínus
1, pretože nechceme, aby

63
00:03:27,780 --> 00:03:29,700
patrí stred sám.

64
00:03:29,700 --> 00:03:34,190
Tak n mínus strednej mínus 1 nám dáva
celkový počet prvkov na pravej strane

65
00:03:34,190 --> 00:03:36,800
stredného indexu v poli.

66
00:03:36,800 --> 00:03:41,870
>> A teraz si uvedomte, že stredná
parameter je hodnota poľa.

67
00:03:41,870 --> 00:03:46,180
Takže tu máme okolo
aktualizovať hodnoty poľa.

68
00:03:46,180 --> 00:03:50,930
Tieto hodnoty, plus stredná plus 1 je
vlastne hovorí rekurzívne volať

69
00:03:50,930 --> 00:03:56,460
vyhľadávanie, odovzdávanie do nového poľa, kde
že nová rada začína v stredu

70
00:03:56,460 --> 00:03:59,370
a jeden z našich pôvodných hodnôt poľa.

71
00:03:59,370 --> 00:04:05,400
>> Alternatívne syntaxe, že teraz
ste začal vidieť odkazy, je

72
00:04:05,400 --> 00:04:10,170
ampersand hodnoty strednej plus 1.

73
00:04:10,170 --> 00:04:17,149
Takže, chytiť adresu stredu
a jeden prvok z hodnôt.

74
00:04:17,149 --> 00:04:23,690
>> Teraz, ak ste neboli pohodlný
zmenou poľa, ako to, že ste

75
00:04:23,690 --> 00:04:28,900
by tiež zaviedli tento používania
rekurzívne funkcie pomocník, kde

76
00:04:28,900 --> 00:04:31,680
že pomocná funkcia sa
viac argumentov.

77
00:04:31,680 --> 00:04:36,610
Takže namiesto toho, aby len hodnoty,
pole, a veľkosť poľa,

78
00:04:36,610 --> 00:04:42,315
pomocná funkcia môže trvať viac
argumenty, vrátane nižším indexom

79
00:04:42,315 --> 00:04:45,280
, Ktorý by sa staral o v poli
a horný index, ktorý vám záleží

80
00:04:45,280 --> 00:04:46,300
o pole.

81
00:04:46,300 --> 00:04:49,770
>> A tak sledovanie aj nižšia
index a horný index, vy nie

82
00:04:49,770 --> 00:04:52,780
je potrebné vždy upraviť
pôvodnej hodnoty poľa.

83
00:04:52,780 --> 00:04:56,390
Môžete len pokračovať
použiť hodnoty poľa.

84
00:04:56,390 --> 00:04:59,540
Ale tu si všimnite, nepotrebujeme pomocníka
fungovať tak dlho, ako budeme

85
00:04:59,540 --> 00:05:01,760
ochotný zmeniť pôvodné
hodnoty poľa.

86
00:05:01,760 --> 00:05:05,020
Sme ochotní odovzdať
aktualizovanej hodnoty.

87
00:05:05,020 --> 00:05:09,140
>> Teraz, nemôžeme binárne hľadanie cez
pole, ktoré je netriedený.

88
00:05:09,140 --> 00:05:12,220
Takže, poďme si to vyrieši.

89
00:05:12,220 --> 00:05:17,650
Teraz si všimnite, že druh je okolo dvoch
parametre int hodnoty, ktorá je

90
00:05:17,650 --> 00:05:21,110
pole, ktoré sme triedenie a int n,
čo je dĺžka poľa, ktoré

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

92
00:05:22,250 --> 00:05:24,840
Takže, tu chceme realizovať
triedenie algoritmus

93
00:05:24,840 --> 00:05:26,690
, Ktorý je o n na druhú.

94
00:05:26,690 --> 00:05:30,560
Tie by mohli zvoliť bubble sort, výber
druh, alebo vloženie triedenia, alebo

95
00:05:30,560 --> 00:05:32,670
nejaký iný druh nemáme
vidieť vo svojej triede.

96
00:05:32,670 --> 00:05:36,380
Ale tu, ideme na
použite pre výber druhu.

97
00:05:36,380 --> 00:05:40,030
>> Takže, budeme iterovat
cez celé pole.

98
00:05:40,030 --> 00:05:44,360
No, tu vidíme, že sme iterácie
od 0 do n mínus 1.

99
00:05:44,360 --> 00:05:45,990
Prečo nie celú cestu až na n?

100
00:05:45,990 --> 00:05:49,320
No, ak sme už je zoradený prvý
n mínus 1 elementy, potom

101
00:05:49,320 --> 00:05:54,420
Posledným prvkom toho, čo už musí byť
na správnom mieste, tak v priebehu radenia

102
00:05:54,420 --> 00:05:56,520
Celé pole.

103
00:05:56,520 --> 00:05:58,770
>> A teraz si uvedomte, ako výber
druh práce.

104
00:05:58,770 --> 00:06:01,950
Chystáme sa ísť cez celé pole
hľadá pre minimálnu hodnotu v

105
00:06:01,950 --> 00:06:04,480
pole a palicu, ktorá
na začiatku.

106
00:06:04,480 --> 00:06:07,610
Potom sme ísť cez celé
pole opäť hľadá sekundu

107
00:06:07,610 --> 00:06:10,410
najmenší prvok, a palica, ktorá
v druhej pozícii v

108
00:06:10,410 --> 00:06:12,100
pole, a tak ďalej.

109
00:06:12,100 --> 00:06:14,330
Tak, to je to, čo to robí.

110
00:06:14,330 --> 00:06:17,290
>> Tu vidíme, že sme
nastavenie aktuálneho minimálna

111
00:06:17,290 --> 00:06:20,030
hodnota indexu i-teho.

112
00:06:20,030 --> 00:06:23,160
Takže v prvej iterácii, ideme
vziať do úvahy minimálna hodnota bude

113
00:06:23,160 --> 00:06:25,030
Začiatok nášho poľa.

114
00:06:25,030 --> 00:06:28,500
Potom budeme iterovat cez
Zvyšok poľa, kontrola na

115
00:06:28,500 --> 00:06:31,870
zistiť, či existuje nejaké prvkami menej ako
jedno, že sme v súčasnej dobe

116
00:06:31,870 --> 00:06:33,900
s ohľadom na minimum.

117
00:06:33,900 --> 00:06:38,840
>> Tak tu, hodnoty j plus jedna - to je
menej než to, čo sme v súčasnej dobe

118
00:06:38,840 --> 00:06:40,380
s ohľadom na minimum.

119
00:06:40,380 --> 00:06:42,940
Potom budeme aktualizovať, čo
si myslíme, že je minimálna, aby

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

121
00:06:44,640 --> 00:06:48,540
Takže, to, že cez celé pole,
a potom, čo to pre slučky, minimálna

122
00:06:48,540 --> 00:06:53,160
by mala byť minimálna prvok z
pozície i-teho v poli.

123
00:06:53,160 --> 00:06:57,350
>> Akonáhle budeme mať, môžeme vymeniť
Minimálna hodnota do pozície i-teho

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

125
00:06:58,230 --> 00:07:00,130
Takže je to len štandardné swap.

126
00:07:00,130 --> 00:07:03,940
Uložíme do dočasnej hodnoty -
hodnota i-ty v poli -

127
00:07:03,940 --> 00:07:08,460
dať do hodnoty i-tého v poli
Minimálna hodnota, ktorá tam patrí,

128
00:07:08,460 --> 00:07:13,580
a potom uložiť späť do ktorých
aktuálna minimálna hodnota býval

129
00:07:13,580 --> 00:07:16,460
i-tá hodnota v poli, tak
že sme nemali stratiť.

130
00:07:16,460 --> 00:07:20,510
>> Tak, že pokračuje
ďalšie iterácii.

131
00:07:20,510 --> 00:07:23,480
Budeme začať hľadať pre druhé
minimálna hodnota a vložiť, že do

132
00:07:23,480 --> 00:07:24,590
druhé miesto.

133
00:07:24,590 --> 00:07:27,440
Na tretej iterácii, sa pozrieme na
Tretie minimálna hodnota a vložka

134
00:07:27,440 --> 00:07:31,550
, Že do tretej polohy, a preto
kým máme zoradené poľa.

135
00:07:31,550 --> 00:07:33,820
Volám sa Rob, a to
bol výber sort.

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