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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Sveiki, aš esu Robas.

3
00:00:15,010 --> 00:00:16,790
Kaip mes naudojame dvejetainio paiešką?

4
00:00:16,790 --> 00:00:18,770
Leiskite sužinoti.

5
00:00:18,770 --> 00:00:23,400
Taigi, atkreipkite dėmesį, kad tai paieškos mes ketiname
rekurencyjnego įgyvendinti.

6
00:00:23,400 --> 00:00:27,470
Jūs taip pat galėtų įgyvendinti binarinę paiešką
keletą kartų, todėl, jei jums padarė, kad

7
00:00:27,470 --> 00:00:29,280
tai puikiai baudą.

8
00:00:29,280 --> 00:00:32,820
>> Dabar pirmiausia, galime prisiminti, kas
parametrai ieškoti yra skirta būti.

9
00:00:32,820 --> 00:00:36,120
Čia mes matome, int verte, kuri yra
turėtų būti vertė vartotojas

10
00:00:36,120 --> 00:00:37,320
ieško.

11
00:00:37,320 --> 00:00:40,800
Matome int reikšmių masyvą, kuris
yra matrica, kurioje mes

12
00:00:40,800 --> 00:00:42,520
ieškoti vertę.

13
00:00:42,520 --> 00:00:45,602
Ir mes matome, int n, kuris yra
mūsų masyvo ilgis.

14
00:00:45,602 --> 00:00:47,410
>> Dabar pirmas dalykas pirmas.

15
00:00:47,410 --> 00:00:51,350
Mes patikrinti, ar n lygus 0, ir
tokiu atveju mes return false.

16
00:00:51,350 --> 00:00:54,770
Tai tiesiog pasakyti, jei mes turime tuščias
masyvas, vertė yra akivaizdžiai ne

17
00:00:54,770 --> 00:00:57,860
tuščias masyvas, todėl mes galime grįžti klaidinga.

18
00:00:57,860 --> 00:01:01,250
>> Dabar mes iš tikrųjų nori daryti dvejetainis
paieška dalis dvejetainėje paiešką.

19
00:01:01,250 --> 00:01:04,780
Taigi, mes norime rasti vidurį
elementas šiame masyve.

20
00:01:04,780 --> 00:01:09,130
Štai, mes sakome, viduriniosios Lygu n suskirstyti
2, nes viduryje elementas yra

21
00:01:09,130 --> 00:01:12,240
bus iš ilgis
mūsų masyvas padalintas iš 2.

22
00:01:12,240 --> 00:01:15,040
Dabar mes ketiname patikrinti, ar
viduryje elementas yra lygi vertei, kurias mes

23
00:01:15,040 --> 00:01:16,160
ieško.

24
00:01:16,160 --> 00:01:21,030
Taigi, jei vertės viduryje Lygu vertę, mes
gali grįžti tiesa, nes mes radome

25
00:01:21,030 --> 00:01:22,810
vertė mūsų masyvo.

26
00:01:22,810 --> 00:01:26,380
>> Bet jei tai buvo tiesa, dabar
mes turime padaryti, grįžtamojo

27
00:01:26,380 --> 00:01:27,840
žingsnis dvejetainėje paiešką.

28
00:01:27,840 --> 00:01:30,450
Mums reikia ieškoti arba į
paliko masyvo arba

29
00:01:30,450 --> 00:01:32,320
viduryje masyvo.

30
00:01:32,320 --> 00:01:39,280
Taigi čia mes sakome, jei vertes viduryje yra
mažiau nei vertės, tai reiškia, kad tą vertę

31
00:01:39,280 --> 00:01:41,350
buvo didesnis nei viduryje
masyvo.

32
00:01:41,350 --> 00:01:45,790
Taigi, vertė turi būti į dešinę
elementas, kad mes tik pažvelgė.

33
00:01:45,790 --> 00:01:48,090
>> Taigi čia mes ketiname
ieškoti rekursyviai.

34
00:01:48,090 --> 00:01:50,320
Ir mes pažvelgti į tai, ką mes artimųjų
tai per sekundę.

35
00:01:50,320 --> 00:01:53,440
Tačiau mes ketiname ieškoti į
teisė viduryje elementas.

36
00:01:53,440 --> 00:01:57,710
O kitu atveju, tai reiškia, kad
vertė buvo mažesnė nei viduryje

37
00:01:57,710 --> 00:02:00,660
masyvas, todėl mes ketiname
ieškoti į kairę.

38
00:02:00,660 --> 00:02:03,520
Dabar, kairėje bus
tiek lengviau pažvelgti.

39
00:02:03,520 --> 00:02:07,770
Taigi, matome, kad čia mes rekursyviai
telefonu paiešką, kur pirmasis

40
00:02:07,770 --> 00:02:10,120
argumentas yra, vėlgi, vertė
mes ieškome daugiau.

41
00:02:10,120 --> 00:02:14,970
Antrasis argumentas bus
matrica, ieškojome naujo.

42
00:02:14,970 --> 00:02:17,090
Ir paskutinis elementas dabar yra viduryje.

43
00:02:17,090 --> 00:02:21,650
Prisiminti paskutinis parametras yra mūsų int
n, todėl tai mūsų masyvo ilgis.

44
00:02:21,650 --> 00:02:25,310
>> Be grįžtamojo skambučio ieškoti, mes
dabar sako, kad ilgis

45
00:02:25,310 --> 00:02:27,230
masyvas yra viduryje.

46
00:02:27,230 --> 00:02:32,900
Taigi, jei mūsų masyvas buvo 20 dydžio, ir mes
ieškoma 10 indeksą, nes viduryje yra

47
00:02:32,900 --> 00:02:36,930
20 padalinti iš 2, tai reiškia, kad mes
einančios 10 kaip nauja

48
00:02:36,930 --> 00:02:38,300
ilgis mūsų masyvo.

49
00:02:38,300 --> 00:02:41,910
Atminkite, kad kai jūs turite masyvą
ilgis 10, tai reiškia, kad galioja

50
00:02:41,910 --> 00:02:45,450
elementai yra indeksų 0 iki 9.

51
00:02:45,450 --> 00:02:50,120
Taigi tai yra būtent tai, ko mes norime
nurodyti atnaujintą mūsų masyvas - kairįjį

52
00:02:50,120 --> 00:02:53,010
masyvas iš viduriniosios elementas.

53
00:02:53,010 --> 00:02:55,710
>> Taigi, žiūrint į dešinę yra
šiek tiek sunkiau.

54
00:02:55,710 --> 00:03:00,170
Dabar pirmiausia aptarkime ilgį
iš į dešinę masyvo

55
00:03:00,170 --> 00:03:01,240
viduryje elementas.

56
00:03:01,240 --> 00:03:08,390
Taigi, jei mūsų masyvas buvo dydžio n, tada
nauja matrica bus dydis n minus

57
00:03:08,390 --> 00:03:10,140
vidutinio atėmus 1.

58
00:03:10,140 --> 00:03:12,530
Taigi, galime galvoti apie n minuso viduryje.

59
00:03:12,530 --> 00:03:18,710
>> Vėlgi, jei masyvas buvo dydžio 20 ir
mes padalinti iš 2 gauti vidurį,

60
00:03:18,710 --> 00:03:23,540
taip viduryje yra 10, tada n atėmus vidutinio
ketina duoti mums 10, taigi 10

61
00:03:23,540 --> 00:03:25,330
elementai į vidurį dešinėje.

62
00:03:25,330 --> 00:03:27,780
Bet mes taip pat turime šį minusą
1, nes mes nenorime

63
00:03:27,780 --> 00:03:29,700
įtraukti vidurį pati.

64
00:03:29,700 --> 00:03:34,190
Taigi n atėmus vidutines atėmus 1 suteikia mums
bendras elementų skaičius į dešinę

65
00:03:34,190 --> 00:03:36,800
viduriniosios indeksas masyve.

66
00:03:36,800 --> 00:03:41,870
>> Dabar čia, atminkite, kad vidutinio
parametras yra vertės masyvo.

67
00:03:41,870 --> 00:03:46,180
Taigi čia mes artimųjų
atnaujinama vertės masyvo.

68
00:03:46,180 --> 00:03:50,930
Šis vertės plius viduriniosios plius 1 yra
faktiškai sakydamas rekursyviai skambinti

69
00:03:50,930 --> 00:03:56,460
paieška, einančios į naują masyvą, kur
kad naujasis masyvas prasideda viduryje

70
00:03:56,460 --> 00:03:59,370
plius vienas iš mūsų pradines reikšmes masyvo.

71
00:03:59,370 --> 00:04:05,400
>> Pakaitinis sintaksė, kad dabar,
jūs pradėjote matyti patarimų, yra

72
00:04:05,400 --> 00:04:10,170
Ampersand vertės viduryje plius 1.

73
00:04:10,170 --> 00:04:17,149
Taigi, patraukti viduryje adresą
plius vienas elementas vertybes.

74
00:04:17,149 --> 00:04:23,690
>> Dabar, jei jums buvo ne patogus
keitimo, kaip kad masyvas, jūs

75
00:04:23,690 --> 00:04:28,900
Taip pat galėjo būti įgyvendintas šis naudojant
rekursywny pagalbininkas funkcija, kur

76
00:04:28,900 --> 00:04:31,680
kad pagalbininkas funkcija trunka
daugiau argumentų.

77
00:04:31,680 --> 00:04:36,610
Taigi vietoj to, reikia atsižvelgti tik į vertę,
masyvas ir masyvo dydis,

78
00:04:36,610 --> 00:04:42,315
pagalbininkas funkcija galėtų būti daugiau
argumentai, įskaitant apatinės rodyklės

79
00:04:42,315 --> 00:04:45,280
kad jūs rūpi masyve
ir viršutinis indeksas, kad jums rūpi

80
00:04:45,280 --> 00:04:46,300
apie masyve.

81
00:04:46,300 --> 00:04:49,770
>> Ir taip nuolat stebėti tiek mažesnis
indeksas ir viršutinis indeksas, jūs neturite

82
00:04:49,770 --> 00:04:52,780
reikia nuolat keisti
pradines reikšmes masyvo.

83
00:04:52,780 --> 00:04:56,390
Jūs galite tiesiog toliau
naudoti reikšmių masyvą.

84
00:04:56,390 --> 00:04:59,540
Bet čia, pranešimas, mums nereikia pagalbininkas
veikti tol, kol mes

85
00:04:59,540 --> 00:05:01,760
nori pakeisti originalą
vertės masyvo.

86
00:05:01,760 --> 00:05:05,020
Mes pasirengę praeiti
Atnaujinta vertės.

87
00:05:05,020 --> 00:05:09,140
>> Dabar, mes negalime binarinę paiešką per
matrica, yra pramaišiui.

88
00:05:09,140 --> 00:05:12,220
Taigi, galime gauti tai sutvarkyti.

89
00:05:12,220 --> 00:05:17,650
Dabar pastebime, kad rūšiuoti pastaruosius dvejus
parametrai int vertybes, kurios yra

90
00:05:17,650 --> 00:05:21,110
matrica, mes rūšiavimo ir int n,
kuris yra masyvo ilgis, kad

91
00:05:21,110 --> 00:05:22,250
mes rūšiavimas.

92
00:05:22,250 --> 00:05:24,840
Taigi, čia mes norime įgyvendinti
rūšiavimo algoritmas

93
00:05:24,840 --> 00:05:26,690
kad yra o n kvadratu.

94
00:05:26,690 --> 00:05:30,560
Jūs galite pasirinkti burbulas rūšiavimo, atrankos
rūšiuoti, ar įterpimo rūšiuoti, arba

95
00:05:30,560 --> 00:05:32,670
kai kitos rūšies turime ne
matyti klasėje.

96
00:05:32,670 --> 00:05:36,380
Bet čia mes ketiname
naudoti atrankos rūšiuoti.

97
00:05:36,380 --> 00:05:40,030
>> Taigi, mes ketiname pakartoti
pagal visą gardelę.

98
00:05:40,030 --> 00:05:44,360
Na, čia mes matome, kad mes Iteracja
nuo 0 iki n atėmus 1.

99
00:05:44,360 --> 00:05:45,990
Kodėl ne visi kelią iki n?

100
00:05:45,990 --> 00:05:49,320
Na, jei mes jau rūšiuojami pirma
n minus 1 elementai, tada

101
00:05:49,320 --> 00:05:54,420
paskutinis elementas, kas jau turi būti
yra teisingoje vietoje, todėl rūšiavimo per

102
00:05:54,420 --> 00:05:56,520
Visas masyvo.

103
00:05:56,520 --> 00:05:58,770
>> Dabar prisimenu, kaip pasirinkimas
rūšiuoti veikia.

104
00:05:58,770 --> 00:06:01,950
Mes ketiname eiti per visą gardelę,
ieško minimalios vertės

105
00:06:01,950 --> 00:06:04,480
masyvas ir lazdas, kad
pradžioje.

106
00:06:04,480 --> 00:06:07,610
Tada mes ketiname eiti per visą
masyvas vėl ieško sekundę

107
00:06:07,610 --> 00:06:10,410
mažiausias elementas, ir lazdas, kad
antroje padėtyje

108
00:06:10,410 --> 00:06:12,100
masyvas ir tt.

109
00:06:12,100 --> 00:06:14,330
Taigi, tai, kas tai daro.

110
00:06:14,330 --> 00:06:17,290
>> Čia mes matome, kad mes
nustatant dabartinius minimalius

111
00:06:17,290 --> 00:06:20,030
vertė i-tojo indekso.

112
00:06:20,030 --> 00:06:23,160
Taigi pirmajame iteracijos, mes ketiname
apsvarstyti minimali vertė turi būti

113
00:06:23,160 --> 00:06:25,030
mūsų masyvo pradžia.

114
00:06:25,030 --> 00:06:28,500
Tada mes ketiname pakartoti per
likusi masyvo, patikrinti,

115
00:06:28,500 --> 00:06:31,870
pamatyti, jei yra kokių nors elementų mažesnis nei
vienas, kad mes šiuo metu

116
00:06:31,870 --> 00:06:33,900
atsižvelgiant į minimalų.

117
00:06:33,900 --> 00:06:38,840
>> Taigi čia, vertybės j plius vienas - tai
mažiau nei tai, ką mes šiuo metu

118
00:06:38,840 --> 00:06:40,380
atsižvelgiant į minimalų.

119
00:06:40,380 --> 00:06:42,940
Tada mes ketiname atnaujinti kas
mes manome, kad yra minimumas

120
00:06:42,940 --> 00:06:44,640
j indeksas plius 1.

121
00:06:44,640 --> 00:06:48,540
Taigi, tai, kad per visą gardelę,
ir po to už kilpos, mažiausiai

122
00:06:48,540 --> 00:06:53,160
turėtų būti minimalus elementas iš
i-asis pozicija masyve.

123
00:06:53,160 --> 00:06:57,350
>> Kai mes turime, kad galėtume sukeisti
minimali vertė į i-osios pozicijos

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

125
00:06:58,230 --> 00:07:00,130
Taigi tai yra tik standartinis apsikeitimo.

126
00:07:00,130 --> 00:07:03,940
Mes laikyti laikina verte -
i-asis vertė masyve -

127
00:07:03,940 --> 00:07:08,460
įdėti į i-osios vertės masyvo
minimali vertė priklauso ten,

128
00:07:08,460 --> 00:07:13,580
ir tada laikyti atgal į kur
anksčiau dabartinė minimali vertė

129
00:07:13,580 --> 00:07:16,460
i-asis vertė masyve, todėl
kad mes ne prarasti.

130
00:07:16,460 --> 00:07:20,510
>> Taigi, kad ir toliau nuo
kitą iteracijos.

131
00:07:20,510 --> 00:07:23,480
Pradėsime ieško sekundę
minimali vertė ir įterpkite į

132
00:07:23,480 --> 00:07:24,590
Antroji pozicija.

133
00:07:24,590 --> 00:07:27,440
Trečią iteracijoje mes ieškome
Trečiasis minimali vertė ir įterpti

134
00:07:27,440 --> 00:07:31,550
kad į trečią vietą, ir taip
tol, kol mes turime surūšiuotą masyvo.

135
00:07:31,550 --> 00:07:33,820
Mano vardas yra Rob, o tai
buvo pasirinkimas rūšiuoti.

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