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

2
00:00:13,300 --> 00:00:15,010
>> ROB Bowden: Živjo, jaz sem Rob.

3
00:00:15,010 --> 00:00:16,790
Kako bomo uporabili binarno iskanje?

4
00:00:16,790 --> 00:00:18,770
Pa poglejmo.

5
00:00:18,770 --> 00:00:23,400
Torej, upoštevajte, da to iskanje gremo
izvajati rekurzivno.

6
00:00:23,400 --> 00:00:27,470
Lahko bi tudi izvajala binarno iskanje
iterativno, tako da, če si to storil,

7
00:00:27,470 --> 00:00:29,280
To je popolnoma v redu.

8
00:00:29,280 --> 00:00:32,820
>> Zdaj prvič, spomnimo se, kaj
Parametri za iskanje so mišljeni.

9
00:00:32,820 --> 00:00:36,120
Tukaj vidimo, int vrednost, ki je
naj bi bila vrednost uporabnik

10
00:00:36,120 --> 00:00:37,320
išče.

11
00:00:37,320 --> 00:00:40,800
Vidimo array int vrednote, ki
je niz, v katerem smo

12
00:00:40,800 --> 00:00:42,520
išče vrednosti.

13
00:00:42,520 --> 00:00:45,602
In vidimo, int n, ki je
Dolžina naše matrike.

14
00:00:45,602 --> 00:00:47,410
>> Zdaj, prva stvar najprej.

15
00:00:47,410 --> 00:00:51,350
Preveriti moramo, da vidim, če je n enak 0, v
tem primeru se vrnemo false.

16
00:00:51,350 --> 00:00:54,770
To je samo rekel, če imamo prazna
matrika, vrednost nedvomno ni v

17
00:00:54,770 --> 00:00:57,860
prazen niz, tako da se lahko vrnemo false.

18
00:00:57,860 --> 00:01:01,250
>> Zdaj smo dejansko želeli narediti binarno
Iskanje del binarnega iskanja.

19
00:01:01,250 --> 00:01:04,780
Torej, želimo, da bi našli sredino
element v tem polju.

20
00:01:04,780 --> 00:01:09,130
Tukaj smo rekli srednji enaka n razdeljen
z 2, saj srednji element

21
00:01:09,130 --> 00:01:12,240
bo dolžina
naš niz deliti z 2.

22
00:01:12,240 --> 00:01:15,040
Zdaj bomo, da preverite, če je
srednji element enaka vrednosti borimo

23
00:01:15,040 --> 00:01:16,160
išče.

24
00:01:16,160 --> 00:01:21,030
Torej, če vrednosti srednji enaka vrednosti, smo
lahko vrne true, saj smo ugotovili,

25
00:01:21,030 --> 00:01:22,810
vrednost v naši matriki.

26
00:01:22,810 --> 00:01:26,380
>> Če pa to ni res, zdaj
moramo narediti rekurzivno

27
00:01:26,380 --> 00:01:27,840
korak binarnega iskanja.

28
00:01:27,840 --> 00:01:30,450
Moramo iskati bodisi
levo matrike ali

29
00:01:30,450 --> 00:01:32,320
Srednji matrike.

30
00:01:32,320 --> 00:01:39,280
Tako da tukaj smo rekli, če vrednosti na sredini je
manjša od vrednosti, ki pomeni, da je vrednost

31
00:01:39,280 --> 00:01:41,350
je večja od sredine
matrike.

32
00:01:41,350 --> 00:01:45,790
Torej mora biti vrednost na desni strani
element, ki smo pravkar pogledal.

33
00:01:45,790 --> 00:01:48,090
>> Torej, tukaj, bomo
iskanje rekurzivno.

34
00:01:48,090 --> 00:01:50,320
In bomo pogledali, kaj smo mimo
to v sekundi.

35
00:01:50,320 --> 00:01:53,440
Ampak bomo iskati za
desno od srednjega elementa.

36
00:01:53,440 --> 00:01:57,710
In v drugem primeru, to pomeni, da
je bila vrednost nižja od sredine

37
00:01:57,710 --> 00:02:00,660
matrika, zato bomo
za iskanje na levi strani.

38
00:02:00,660 --> 00:02:03,520
Zdaj, leva se bo
nekoliko lažje gledati.

39
00:02:03,520 --> 00:02:07,770
Torej, vidimo tukaj, da smo rekurzivno
kliče iskanje kjer prvi

40
00:02:07,770 --> 00:02:10,120
argument je, še enkrat, vrednost
iščemo več.

41
00:02:10,120 --> 00:02:14,970
Drugi argument, ki se bo
matrika, ki smo iskali več.

42
00:02:14,970 --> 00:02:17,090
In zadnji element je zdaj srednja.

43
00:02:17,090 --> 00:02:21,650
Ne pozabite, zadnji parameter je naša int
n, tako da je dolžina našega matrike.

44
00:02:21,650 --> 00:02:25,310
>> V rekurzivnega klica za iskanje, smo
Zdaj pravijo, da dolžina

45
00:02:25,310 --> 00:02:27,230
Niz je srednja.

46
00:02:27,230 --> 00:02:32,900
Torej, če je bila naša paleta velikosti 20 in smo
Iskali pri indeksu 10, saj je srednji

47
00:02:32,900 --> 00:02:36,930
20 deljeno z 2, kar pomeni, da smo
poteka 10 kot nova

48
00:02:36,930 --> 00:02:38,300
Dolžina naše matrike.

49
00:02:38,300 --> 00:02:41,910
Ne pozabite, da če imate niz
dolžine 10, kar pomeni, da velja

50
00:02:41,910 --> 00:02:45,450
elementi so indeksi od 0 do 9.

51
00:02:45,450 --> 00:02:50,120
Torej, to je točno tisto, kar smo želeli
določajo našo posodobljeno paleto - levo

52
00:02:50,120 --> 00:02:53,010
matrika iz srednjega elementa.

53
00:02:53,010 --> 00:02:55,710
>> Torej, je videti na desni strani je
nekoliko težje.

54
00:02:55,710 --> 00:03:00,170
Zdaj najprej, kaj je upoštevati dolžino
matrike na desni strani

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

56
00:03:01,240 --> 00:03:08,390
Torej, če je bila naša paleta velikosti n, potem
Nova matrika bo v velikosti n minusom

57
00:03:08,390 --> 00:03:10,140
srednji minus 1.

58
00:03:10,140 --> 00:03:12,530
Torej, kaj je razmišljati n minus sredini.

59
00:03:12,530 --> 00:03:18,710
>> Again, če bi bila matrika velikosti 20 in
delimo z 2, da bi dobili na sredini,

60
00:03:18,710 --> 00:03:23,540
Tako srednji je 10, potem je n minus srednji
se dogaja, da nam je 10, torej 10

61
00:03:23,540 --> 00:03:25,330
Elementi na desni sredini.

62
00:03:25,330 --> 00:03:27,780
Vendar imamo tudi ta minus
1, saj ne želimo, da se

63
00:03:27,780 --> 00:03:29,700
vključujejo sredini sam.

64
00:03:29,700 --> 00:03:34,190
Torej n minus srednja minus 1 pa nas daje
Skupno število elementov v desno

65
00:03:34,190 --> 00:03:36,800
srednjega indeksa v matriki.

66
00:03:36,800 --> 00:03:41,870
>> Zdaj tukaj, ne pozabite, da srednji
parameter je niz vrednosti.

67
00:03:41,870 --> 00:03:46,180
Tako da tukaj smo vrtaš
posodobljene vrednosti matrike.

68
00:03:46,180 --> 00:03:50,930
Te vrednosti plus srednji plus 1 je
dejansko rekel rekurzivno pokličite

69
00:03:50,930 --> 00:03:56,460
iskanje, ki poteka v novem polju, kjer
da nova mreža začne v sredini

70
00:03:56,460 --> 00:03:59,370
plus eden od naših prvotne vrednosti matrike.

71
00:03:59,370 --> 00:04:05,400
>> Nadomestnega sintaksa za to, zdaj,
Začeli ste videli kazalci, je

72
00:04:05,400 --> 00:04:10,170
ampersand vrednosti srednji plus 1.

73
00:04:10,170 --> 00:04:17,149
Torej, zgrabite naslov sredini
plus en element vrednot.

74
00:04:17,149 --> 00:04:23,690
>> Zdaj, če ne bi bilo udobno
spreminjanje paleto, kot je ta, boste

75
00:04:23,690 --> 00:04:28,900
Lahko bi tudi izvajala to uporabo
rekurzivna funkcija pomočnik, kjer

76
00:04:28,900 --> 00:04:31,680
to funkcijo pomočnika traja
več argumentov.

77
00:04:31,680 --> 00:04:36,610
Torej, namesto da bi samo vrednost,
matrika in velikostjo polja,

78
00:04:36,610 --> 00:04:42,315
Funkcija pomočnik lahko traja več
trditev tudi spodnji indeks

79
00:04:42,315 --> 00:04:45,280
da bi vas skrbi v matriki
in zgornji indeks, ki vam ni vseeno

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

81
00:04:46,300 --> 00:04:49,770
>> In tako sledenja tako nižja
indeks in zgornji indeks, pa ne

82
00:04:49,770 --> 00:04:52,780
morali kdaj spremeniti
izvirne vrednosti matrike.

83
00:04:52,780 --> 00:04:56,390
Lahko samo še
uporabite niz vrednot.

84
00:04:56,390 --> 00:04:59,540
Ampak tukaj, opazili ne potrebujemo pomočnika
delujejo tako dolgo, kot smo

85
00:04:59,540 --> 00:05:01,760
pripravljeni spremeniti izvirnik
Vrednosti matrike.

86
00:05:01,760 --> 00:05:05,020
Mi smo pripravljeni, da prenese v
an dodani vrednosti.

87
00:05:05,020 --> 00:05:09,140
>> Zdaj ne moremo binarno iskanje na
matrika, ki je, razvrščeni.

88
00:05:09,140 --> 00:05:12,220
Torej, kaj je dobil to urejeno.

89
00:05:12,220 --> 00:05:17,650
Zdaj, opazili, da je nekako mimo dveh
parametri int vrednosti, ki je

90
00:05:17,650 --> 00:05:21,110
matrika, ki smo razvrščanje in int n,
ki je dolžina polja, ki

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

92
00:05:22,250 --> 00:05:24,840
Torej, tukaj želimo izvajati
sortiranje algoritem

93
00:05:24,840 --> 00:05:26,690
da je o n kvadrat.

94
00:05:26,690 --> 00:05:30,560
Lahko izbirate mehurček sortiranje, izbor
sort, ali vstavljanje sort, ali

95
00:05:30,560 --> 00:05:32,670
nekatere druge vrste nismo
videli v razredu.

96
00:05:32,670 --> 00:05:36,380
Ampak tukaj, gremo na
uporabite za izbiro vrste.

97
00:05:36,380 --> 00:05:40,030
>> Torej, bomo Ponovil
prek celotnega niza.

98
00:05:40,030 --> 00:05:44,360
No, pa smo videli, da smo ponavljanjem
od 0 do n minus 1.

99
00:05:44,360 --> 00:05:45,990
Zato ni vse tja do n?

100
00:05:45,990 --> 00:05:49,320
No, če smo že razporejene prvi
n minus 1 elemente, nato

101
00:05:49,320 --> 00:05:54,420
Zelo zadnji element, kaj mora že biti
v pravem mestu, tako sortiranje nad

102
00:05:54,420 --> 00:05:56,520
celoten niz.

103
00:05:56,520 --> 00:05:58,770
>> Vedeti moramo, kako izbira
nekako deluje.

104
00:05:58,770 --> 00:06:01,950
Mi smo šli prek celotnega niza
išče najmanjšo vrednost v

105
00:06:01,950 --> 00:06:04,480
matrika in palico, ki
na začetku.

106
00:06:04,480 --> 00:06:07,610
Potem smo šli v celotnem obdobju
Niz spet iščejo drugi

107
00:06:07,610 --> 00:06:10,410
najmanjši element, in palico, ki
v drugem položaju v

108
00:06:10,410 --> 00:06:12,100
matrika, in tako naprej.

109
00:06:12,100 --> 00:06:14,330
Torej, to je tisto, kar to počne.

110
00:06:14,330 --> 00:06:17,290
>> Tukaj smo videli, da smo
postavimo trenutni minimum

111
00:06:17,290 --> 00:06:20,030
vrednost indeksa i-tega.

112
00:06:20,030 --> 00:06:23,160
Torej na prvi ponovitvi, gremo
preučiti minimalno vrednost, da se

113
00:06:23,160 --> 00:06:25,030
začetek našega array.

114
00:06:25,030 --> 00:06:28,500
Nato bomo Ponovil več
Preostali del matrike, preverjanje, da

115
00:06:28,500 --> 00:06:31,870
glej če obstajajo elementi manjši od
tisti, ki smo trenutno

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

117
00:06:33,900 --> 00:06:38,840
>> Torej, tukaj, vrednote j plus eno - to je
manj, kot smo trenutno

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

119
00:06:40,380 --> 00:06:42,940
Potem bomo posodobiti, kar
mislimo, da je najmanjše

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

121
00:06:44,640 --> 00:06:48,540
Torej, da je v celotnem polju,
in potem to za zanke, najmanj

122
00:06:48,540 --> 00:06:53,160
mora biti minimalna element iz
Položaj i-ti v matriki.

123
00:06:53,160 --> 00:06:57,350
>> Ko bomo imeli, da bomo lahko swap
najmanjša vrednost v položaj i-

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

125
00:06:58,230 --> 00:07:00,130
Torej to je samo standardni swap.

126
00:07:00,130 --> 00:07:03,940
Hranimo v začasni vrednosti -
Vrednost i-ti v matriki -

127
00:07:03,940 --> 00:07:08,460
dajo v vrednosti i-tega v matriki
najmanjša vrednost, ki sodi tja,

128
00:07:08,460 --> 00:07:13,580
in nato shranjevanje nazaj v kadar
Sedanja minimalna vrednost, s katero se

129
00:07:13,580 --> 00:07:16,460
i-ta vrednost v matriki, tako
da nismo izgubili.

130
00:07:16,460 --> 00:07:20,510
>> Tako, da se nadaljuje
Naslednja ponovitev.

131
00:07:20,510 --> 00:07:23,480
Bomo začeli iskati drugo
Najnižja vrednost in vstavite, da v

132
00:07:23,480 --> 00:07:24,590
drugi položaj.

133
00:07:24,590 --> 00:07:27,440
Na tretji ponovitvi, bomo iskali
tretja najnižja vrednost in vložek

134
00:07:27,440 --> 00:07:31,550
da v tretjem položaju, in tako
dokler imamo urejen niz.

135
00:07:31,550 --> 00:07:33,820
Moje ime je Rob, in to
je bil izbor sort.

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