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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Ahoj, já jsem Rob.

3
00:00:15,010 --> 00:00:16,790
Jak používáme binární hledání?

4
00:00:16,790 --> 00:00:18,770
Pojďme zjistit.

5
00:00:18,770 --> 00:00:23,400
Takže, na vědomí, že toto hledání jedeme
provádět rekurzivně.

6
00:00:23,400 --> 00:00:27,470
Dalo by se také provádět binární vyhledávání
iterativně, takže pokud to uděláte,

7
00:00:27,470 --> 00:00:29,280
To je naprosto v pořádku.

8
00:00:29,280 --> 00:00:32,820
>> Nyní poprvé, pojďme si vzpomenout, co
Parametry pro hledání mají být.

9
00:00:32,820 --> 00:00:36,120
Zde vidíme int hodnotu, která je
má být hodnota uživatel

10
00:00:36,120 --> 00:00:37,320
vyhledávání.

11
00:00:37,320 --> 00:00:40,800
Vidíme pole int hodnoty, které
je pole, ve kterém jsme

12
00:00:40,800 --> 00:00:42,520
hledá hodnotu.

13
00:00:42,520 --> 00:00:45,602
A vidíme, int n, což je
délka našeho pole.

14
00:00:45,602 --> 00:00:47,410
>> Nyní, první věc, kterou jako první.

15
00:00:47,410 --> 00:00:51,350
Zkontrolujte jsme se zjistit, jestli n se rovná 0, se
takovém případě se vrátíme false.

16
00:00:51,350 --> 00:00:54,770
To jen říkám, máme-li prázdná
pole, hodnota je jednoznačně není

17
00:00:54,770 --> 00:00:57,860
prázdné pole, takže se můžeme vrátit false.

18
00:00:57,860 --> 00:01:01,250
>> Teď jsme vlastně chcete udělat binární
Vyhledávání součástí binárního vyhledávání.

19
00:01:01,250 --> 00:01:04,780
Takže, chceme najít střed
prvek tohoto pole.

20
00:01:04,780 --> 00:01:09,130
Zde říkáme, střední rovná n dělí
o 2, protože prostřední element je

21
00:01:09,130 --> 00:01:12,240
bude délka
naše pole děleno 2.

22
00:01:12,240 --> 00:01:15,040
Teď budeme kontrolovat, zda
prostřední element rovná hodnotě stojíme

23
00:01:15,040 --> 00:01:16,160
vyhledávání.

24
00:01:16,160 --> 00:01:21,030
Takže pokud hodnoty střední rovná hodnotě, jsme
může vrátit true, protože jsme zjistili, že

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

26
00:01:22,810 --> 00:01:26,380
>> Ale v případě, že to není pravda, teď
musíme udělat rekurzivní

27
00:01:26,380 --> 00:01:27,840
krok binární vyhledávání.

28
00:01:27,840 --> 00:01:30,450
Musíme hledat buď
vlevo na pole nebo na

29
00:01:30,450 --> 00:01:32,320
uprostřed pole.

30
00:01:32,320 --> 00:01:39,280
Tak tady, můžeme říci, že hodnoty na střed je
menší než hodnota, která znamená, že hodnota

31
00:01:39,280 --> 00:01:41,350
byl větší než uprostřed
z pole.

32
00:01:41,350 --> 00:01:45,790
Takže hodnota musí být vpravo
prvek, který jsme právě podíval na.

33
00:01:45,790 --> 00:01:48,090
>> Tak tady, jedeme na
hledat rekurzivně.

34
00:01:48,090 --> 00:01:50,320
A my se podíváme na to, co jsme kolem
k tomu v druhém.

35
00:01:50,320 --> 00:01:53,440
Ale budeme hledat na
vpravo od středního prvku.

36
00:01:53,440 --> 00:01:57,710
A v druhém případě, to znamená, že
hodnota byla nižší než uprostřed

37
00:01:57,710 --> 00:02:00,660
pole, a tak jdeme
hledat na levé straně.

38
00:02:00,660 --> 00:02:03,520
Nyní, vlevo bude
trochu jednodušší podívat se na.

39
00:02:03,520 --> 00:02:07,770
Takže, zde vidíme, že jsme rekurzivně
volání, kde první hledání

40
00:02:07,770 --> 00:02:10,120
argument je opět hodnota
díváme přes.

41
00:02:10,120 --> 00:02:14,970
Druhý argument se bude
pole, které jsme hledali přes.

42
00:02:14,970 --> 00:02:17,090
A poslední prvek je nyní uprostřed.

43
00:02:17,090 --> 00:02:21,650
Nezapomeňte, poslední parametr je naše int
n, tak to je délka našeho pole.

44
00:02:21,650 --> 00:02:25,310
>> V rekurzivní volání pro hledání, jsme
Nyní říká, že délka

45
00:02:25,310 --> 00:02:27,230
pole je střední.

46
00:02:27,230 --> 00:02:32,900
Takže, pokud naše pole bylo o velikosti 20 a my
hledal na index 10, protože střed je

47
00:02:32,900 --> 00:02:36,930
20 děleno 2, to znamená, že jsme
kolem 10 jako nový

48
00:02:36,930 --> 00:02:38,300
délka našeho pole.

49
00:02:38,300 --> 00:02:41,910
Pamatujte si, že když máte pole
délky 10, to znamená, že platí

50
00:02:41,910 --> 00:02:45,450
prvky jsou v indexech 0 až 9.

51
00:02:45,450 --> 00:02:50,120
Tak to je přesně to, co chceme
specifikovat náš aktualizovaný pole - levé

52
00:02:50,120 --> 00:02:53,010
pole od středu prvku.

53
00:02:53,010 --> 00:02:55,710
>> Takže, hledá na pravé straně je
trochu složitější.

54
00:02:55,710 --> 00:03:00,170
Nyní poprvé, pojďme zvážit délku
z pole na pravé straně

55
00:03:00,170 --> 00:03:01,240
prostřední prvek.

56
00:03:01,240 --> 00:03:08,390
Takže, pokud naše pole bylo velikosti n, pak
Nová řada bude mít velikost n mínus

57
00:03:08,390 --> 00:03:10,140
střední minus 1.

58
00:03:10,140 --> 00:03:12,530
Takže, pojďme si n mínus uprostřed.

59
00:03:12,530 --> 00:03:18,710
>> Opět platí, že v případě, že pole byla velikosti 20 a
dělíme o 2 dostat střed,

60
00:03:18,710 --> 00:03:23,540
takže uprostřed je 10, pak n minus střední
bude nám 10, takže 10

61
00:03:23,540 --> 00:03:25,330
prvky napravo od středu.

62
00:03:25,330 --> 00:03:27,780
Ale máme také tuto minus
1, protože nechceme, aby

63
00:03:27,780 --> 00:03:29,700
patří střed sám.

64
00:03:29,700 --> 00:03:34,190
Tak n minus střední minus 1 nám dává
celkový počet prvků na pravé straně

65
00:03:34,190 --> 00:03:36,800
středního indexu v poli.

66
00:03:36,800 --> 00:03:41,870
>> A teď si uvědomte, že střední
parametr je hodnota pole.

67
00:03:41,870 --> 00:03:46,180
Takže tady máme kolem
aktualizovat hodnoty pole.

68
00:03:46,180 --> 00:03:50,930
Tyto hodnoty, plus střední plus 1 je
vlastně říká rekurzivně volat

69
00:03:50,930 --> 00:03:56,460
vyhledávání, předávání do nového pole, kde
že nová řada začíná ve středu

70
00:03:56,460 --> 00:03:59,370
a jeden z našich původních hodnot pole.

71
00:03:59,370 --> 00:04:05,400
>> Alternativní syntaxe, že nyní
jste začal vidět odkazy, je

72
00:04:05,400 --> 00:04:10,170
ampersand hodnoty střední plus 1.

73
00:04:10,170 --> 00:04:17,149
Takže, chytit adresu středu
a jeden prvek z hodnot.

74
00:04:17,149 --> 00:04:23,690
>> Nyní, pokud jste nebyli pohodlný
změnou pole, jako to, že jste

75
00:04:23,690 --> 00:04:28,900
by také zavedli tento používání
rekurzivní funkce pomocník, kde

76
00:04:28,900 --> 00:04:31,680
že pomocná funkce se
více argumentů.

77
00:04:31,680 --> 00:04:36,610
Takže místo toho, aby jen hodnoty,
pole, a velikost pole,

78
00:04:36,610 --> 00:04:42,315
pomocná funkce může trvat více
argumenty, včetně nižším indexem

79
00:04:42,315 --> 00:04:45,280
, který by se staral o v poli
a horní index, který 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 sledování i nižší
index a horní index, vy ne

82
00:04:49,770 --> 00:04:52,780
je třeba vždy upravit
původní hodnoty pole.

83
00:04:52,780 --> 00:04:56,390
Můžete jen pokračovat
použít hodnoty pole.

84
00:04:56,390 --> 00:04:59,540
Ale tady si všimněte, nepotřebujeme pomocníka
fungovat tak dlouho, jak budeme

85
00:04:59,540 --> 00:05:01,760
ochoten změnit původní
hodnoty pole.

86
00:05:01,760 --> 00:05:05,020
Jsme ochotni předat
aktualizované hodnoty.

87
00:05:05,020 --> 00:05:09,140
>> Nyní, nemůžeme binární hledání přes
pole, které je netříděný.

88
00:05:09,140 --> 00:05:12,220
Takže, pojďme si to vyřeší.

89
00:05:12,220 --> 00:05:17,650
Nyní si všimněte, že druh je kolem dvou
parametry int hodnoty, která je

90
00:05:17,650 --> 00:05:21,110
pole, které jsme třídění a int n,
což je délka pole, které

91
00:05:21,110 --> 00:05:22,250
jsme třídění.

92
00:05:22,250 --> 00:05:24,840
Takže, tady chceme realizovat
třídění algoritmus

93
00:05:24,840 --> 00:05:26,690
, který je o n na druhou.

94
00:05:26,690 --> 00:05:30,560
Ty by mohly zvolit bubble sort, výběr
druh, nebo vložení třídění, nebo

95
00:05:30,560 --> 00:05:32,670
nějaký jiný druh nemáme
vidět ve své třídě.

96
00:05:32,670 --> 00:05:36,380
Ale tady, jedeme na
použijte pro výběr druhu.

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

98
00:05:40,030 --> 00:05:44,360
No, tady vidíme, že jsme iterace
od 0 do n minus 1.

99
00:05:44,360 --> 00:05:45,990
Proč ne celou cestu až na n?

100
00:05:45,990 --> 00:05:49,320
No, pokud jsme již řazeno první
n mínus 1 elementy, pak

101
00:05:49,320 --> 00:05:54,420
Posledním prvkem toho, co již musí být
na správném místě, tak v průběhu řazení

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

103
00:05:56,520 --> 00:05:58,770
>> A teď si uvědomte, jak výběr
druh práce.

104
00:05:58,770 --> 00:06:01,950
Chystáme se jet přes celé pole
hledá pro minimální hodnotu v

105
00:06:01,950 --> 00:06:04,480
pole a hůl, která
na začátku.

106
00:06:04,480 --> 00:06:07,610
Pak jsme jít přes celé
pole opět hledá sekundu

107
00:06:07,610 --> 00:06:10,410
nejmenší prvek, a hůl, která
ve druhé pozici v

108
00:06:10,410 --> 00:06:12,100
pole, a tak dále.

109
00:06:12,100 --> 00:06:14,330
Tak, to je to, co to dělá.

110
00:06:14,330 --> 00:06:17,290
>> Zde vidíme, že jsme
nastavení aktuálního minimální

111
00:06:17,290 --> 00:06:20,030
hodnota indexu i-tého.

112
00:06:20,030 --> 00:06:23,160
Takže v první iteraci, jedeme
vzít v úvahu minimální hodnota bude

113
00:06:23,160 --> 00:06:25,030
Začátek našeho pole.

114
00:06:25,030 --> 00:06:28,500
Pak budeme iterovat přes
Zbytek pole, kontrola na

115
00:06:28,500 --> 00:06:31,870
zjistit, jestli existuje nějaké prvky menší než
jedno, že jsme v současné době

116
00:06:31,870 --> 00:06:33,900
s ohledem na minimum.

117
00:06:33,900 --> 00:06:38,840
>> Tak tady, hodnoty j plus jedna - to je
méně než to, co jsme v současné době

118
00:06:38,840 --> 00:06:40,380
s ohledem na minimum.

119
00:06:40,380 --> 00:06:42,940
Pak budeme aktualizovat, co
si myslíme, že je minimální, 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 přes celé pole,
a poté, co to pro smyčky, minimální

122
00:06:48,540 --> 00:06:53,160
by měla být minimální prvek z
pozice i-tého v poli.

123
00:06:53,160 --> 00:06:57,350
>> Jakmile budeme mít, můžeme vyměnit
Minimální hodnota do pozice i-tého

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

125
00:06:58,230 --> 00:07:00,130
Takže je to jen standardní swap.

126
00:07:00,130 --> 00:07:03,940
Uložíme do dočasné hodnoty -
hodnota i-tý v poli -

127
00:07:03,940 --> 00:07:08,460
dát do hodnoty i-tého v poli
Minimální hodnota, která tam patří,

128
00:07:08,460 --> 00:07:13,580
a poté uložit zpět do kterých
aktuální minimální hodnota býval

129
00:07:13,580 --> 00:07:16,460
i-tá hodnota v poli, tak
že jsme neměli ztratit.

130
00:07:16,460 --> 00:07:20,510
>> Tak, že pokračuje
další iteraci.

131
00:07:20,510 --> 00:07:23,480
Budeme začít hledat pro druhé
minimální hodnota a vložit, že do

132
00:07:23,480 --> 00:07:24,590
druhé místo.

133
00:07:24,590 --> 00:07:27,440
Na třetí iteraci, se podíváme na
Třetí minimální hodnota a vložka

134
00:07:27,440 --> 00:07:31,550
, že do třetí polohy, a proto
dokud máme seřazené pole.

135
00:07:31,550 --> 00:07:33,820
Jmenuji se Rob, a to
byl výběr sort.

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