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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Sveiki, es esmu Rob.

3
00:00:15,010 --> 00:00:16,790
Kā mēs izmantot bināro meklēšanu?

4
00:00:16,790 --> 00:00:18,770
Let 's uzzināt.

5
00:00:18,770 --> 00:00:23,400
Tātad, ņemiet vērā, ka šo meklējumu mēs ejam
īstenot rekursīvi.

6
00:00:23,400 --> 00:00:27,470
Jūs varētu arī īstenot bināro meklēšanu
iteratīvi, tādēļ, ja jūs, ka,

7
00:00:27,470 --> 00:00:29,280
tas ir pilnīgi naudas sodu.

8
00:00:29,280 --> 00:00:32,820
>> Tagad pirmo reizi, atcerēsimies, kāda
parametrus, lai meklētu, ir domāts, lai būtu.

9
00:00:32,820 --> 00:00:36,120
Šeit mēs redzam, int vērtību, kas ir
vajadzētu būt vērtība ir lietotājs

10
00:00:36,120 --> 00:00:37,320
meklē.

11
00:00:37,320 --> 00:00:40,800
Mēs redzam, ka int vērtības masīvs, kas
ir masīvs, kurā mēs esam

12
00:00:40,800 --> 00:00:42,520
meklējot vērtības.

13
00:00:42,520 --> 00:00:45,602
Un mēs redzam, int n, kas ir
garums mūsu masīvs.

14
00:00:45,602 --> 00:00:47,410
>> Tagad, pirmā lieta, pirmkārt.

15
00:00:47,410 --> 00:00:51,350
Mēs pārbaudām, vai n ir vienāds ar 0, jo
un tādā gadījumā mēs atgriežamies nepatiesa.

16
00:00:51,350 --> 00:00:54,770
Tas ir tikai saprotams, ja mums ir tukšs
masīvs, vērtība ir acīmredzami nav

17
00:00:54,770 --> 00:00:57,860
tukšs masīvs, lai mēs varētu atgriezties viltus.

18
00:00:57,860 --> 00:01:01,250
>> Tagad mēs patiešām vēlamies darīt bināro
meklēšana daļa bināro meklēšanu.

19
00:01:01,250 --> 00:01:04,780
Tātad, mēs vēlamies, lai atrastu vidū
Šī masīva elements.

20
00:01:04,780 --> 00:01:09,130
Lūk, mēs sakām vidū ir vienāds ar n dalīts
ar 2, jo vidus elements ir

21
00:01:09,130 --> 00:01:12,240
būs garums
Mūsu masīvs dalīts ar 2.

22
00:01:12,240 --> 00:01:15,040
Tagad mēs esam gatavojas pārbaudīt, lai redzētu, vai
vidū elements ir vienāds ar vērtību, mēs esat

23
00:01:15,040 --> 00:01:16,160
meklē.

24
00:01:16,160 --> 00:01:21,030
Tātad, ja vērtības vidū ir vienāda vērtība, mēs
var atgriezties taisnība, jo mēs atradām

25
00:01:21,030 --> 00:01:22,810
vērtība mūsu masīvā.

26
00:01:22,810 --> 00:01:26,380
>> Bet, ja tas nav taisnība, tagad
mums ir jādara rekursīvs

27
00:01:26,380 --> 00:01:27,840
solis bināro meklēšanu.

28
00:01:27,840 --> 00:01:30,450
Mums ir jāmeklē vai nu
kreisi no masīva vai

29
00:01:30,450 --> 00:01:32,320
vidū masīva.

30
00:01:32,320 --> 00:01:39,280
Tātad šeit, mēs sakām, ja vērtības, kas pa vidu ir
mazāk nekā vērtība, tas nozīmē, ka šo vērtību

31
00:01:39,280 --> 00:01:41,350
ir lielāks nekā vidu
masīva.

32
00:01:41,350 --> 00:01:45,790
Tā vērtība ir jābūt tiesībām
elements, ka mēs vienkārši paskatījās.

33
00:01:45,790 --> 00:01:48,090
>> Tātad šeit mēs gatavojamies
meklēt rekursīvi.

34
00:01:48,090 --> 00:01:50,320
Un mēs apskatīt to, ko mēs esam iet
uz šo sekundē.

35
00:01:50,320 --> 00:01:53,440
Bet mēs ejam meklēt, lai
tiesības vidū elementa.

36
00:01:53,440 --> 00:01:57,710
Un otrā gadījumā tas nozīmē, ka
vērtība ir mazāka nekā vidū

37
00:01:57,710 --> 00:02:00,660
masīvs, un tā mēs ejam
meklēt pa kreisi.

38
00:02:00,660 --> 00:02:03,520
Tagad, pa kreisi būs
mazliet vieglāk apskatīt.

39
00:02:03,520 --> 00:02:07,770
Tātad, mēs redzam šeit, ka mēs esam rekursīvi
aicinot meklēt, kur pirmais

40
00:02:07,770 --> 00:02:10,120
arguments ir, atkal, vērtība
mēs meklējam vairāk.

41
00:02:10,120 --> 00:02:14,970
Otrais arguments būs
masīvs, ka mēs meklēt vairāk.

42
00:02:14,970 --> 00:02:17,090
Un pēdējais elements tagad vidū.

43
00:02:17,090 --> 00:02:21,650
Atcerieties pēdējais parametrs ir mūsu int
n, tā ka ir garums mūsu masīvs.

44
00:02:21,650 --> 00:02:25,310
>> Ar rekursīvas zvanu, lai meklētu, mēs esam
tagad saka, ka garums

45
00:02:25,310 --> 00:02:27,230
masīvs ir vidū.

46
00:02:27,230 --> 00:02:32,900
Tātad, ja mūsu masīvs bija lieluma 20 un mēs
meklēja pie indeksu 10, jo pa vidu ir

47
00:02:32,900 --> 00:02:36,930
20 dalīts ar 2, tas nozīmē, ka mēs esam
iet 10, jo jaunā

48
00:02:36,930 --> 00:02:38,300
garums mūsu masīvs.

49
00:02:38,300 --> 00:02:41,910
Atcerieties, ka, ja jums ir masīvs
garuma 10, tas nozīmē, ka ir spēkā

50
00:02:41,910 --> 00:02:45,450
elementi ir indeksiem 0 līdz 9.

51
00:02:45,450 --> 00:02:50,120
Tātad, tas ir tieši tas, ko mēs vēlamies, lai
precizēt mūsu atjaunināto masīvs - kreiso

52
00:02:50,120 --> 00:02:53,010
masīvs no vidējā elementa.

53
00:02:53,010 --> 00:02:55,710
>> Tātad, meklē labi ir
mazliet grūtāk.

54
00:02:55,710 --> 00:03:00,170
Tagad pirmo reizi, pieņemsim apsvērt garumu
masīva uz tiesībām

55
00:03:00,170 --> 00:03:01,240
vidū elements.

56
00:03:01,240 --> 00:03:08,390
Tātad, ja mūsu masīvs bija lieluma n, tad
Jaunais masīvs būs lielums n mīnusu

57
00:03:08,390 --> 00:03:10,140
vidējā mīnus 1.

58
00:03:10,140 --> 00:03:12,530
Tātad, pieņemsim domāt n mīnus vidū.

59
00:03:12,530 --> 00:03:18,710
>> Atkal, ja masīvs bija lieluma 20 un
mēs sadalīt pa 2, lai iegūtu vidū,

60
00:03:18,710 --> 00:03:23,540
tā vidū ir 10, tad n mīnus vidū
gatavojas sniegt mums 10, tāpēc 10

61
00:03:23,540 --> 00:03:25,330
elementi pa labi pa vidu.

62
00:03:25,330 --> 00:03:27,780
Bet mums arī ir šī mīnus
1, jo mēs nevēlamies

63
00:03:27,780 --> 00:03:29,700
ietver vidū pati.

64
00:03:29,700 --> 00:03:34,190
Tātad n mīnus vidējā mīnus 1 dod mums
kopskaits elementu labās

65
00:03:34,190 --> 00:03:36,800
no vidējā indeksa masīvā.

66
00:03:36,800 --> 00:03:41,870
>> Tagad šeit, atcerieties, ka vidējā
parametrs ir vērtību masīvs.

67
00:03:41,870 --> 00:03:46,180
Tātad šeit mēs iet
papildināta vērtības masīvs.

68
00:03:46,180 --> 00:03:50,930
Šis vērtības plus vidējā plus 1 ir
patiesībā sakot rekursīvi zvaniet

69
00:03:50,930 --> 00:03:56,460
meklēšana, kas iet jaunā masīvs, kur
ka jaunā masīva sākas vidū

70
00:03:56,460 --> 00:03:59,370
plus viens no mūsu sākotnējās vērtības bloku.

71
00:03:59,370 --> 00:04:05,400
>> Aizstājējs sintakse, ka tagad,
Jūs esat sācis redzēt norādes, ir

72
00:04:05,400 --> 00:04:10,170
Ampersand vērtību vidū, kā arī 1.

73
00:04:10,170 --> 00:04:17,149
Tātad, greifers adresi vidū
plus viens elements no vērtībām.

74
00:04:17,149 --> 00:04:23,690
>> Tagad, ja jūs neesat apmierināti
pārveidojot masīvu, piemēram, ka jūs

75
00:04:23,690 --> 00:04:28,900
arī varētu būt īstenoti to, izmantojot
rekursīvs palīgs funkcija, kur

76
00:04:28,900 --> 00:04:31,680
ka palīgs funkcija tiek
vairāk argumenti.

77
00:04:31,680 --> 00:04:36,610
Tā vietā, lai veiktu tikai vērtību,
masīvs, un lielumu masīva,

78
00:04:36,610 --> 00:04:42,315
palīgs funkcijas varētu uzņemties vairāk
argumentus, tajā skaitā zemāko indeksu

79
00:04:42,315 --> 00:04:45,280
ka jūs varētu rūpēties par masīvā
un augšējo indeksu, ka jūs aprūpi

80
00:04:45,280 --> 00:04:46,300
par masīvu.

81
00:04:46,300 --> 00:04:49,770
>> Un tā sekotu gan zemākas
indekss un augšējo indeksu, jums nav

82
00:04:49,770 --> 00:04:52,780
nepieciešams, lai kādreiz mainīt
sākotnējās vērtības masīvs.

83
00:04:52,780 --> 00:04:56,390
Jūs varat turpināt
izmantot vērtības masīvu.

84
00:04:56,390 --> 00:04:59,540
Bet šeit, paziņojums mums nav vajadzīgs palīgs
darboties tik ilgi, kamēr mēs esam

85
00:04:59,540 --> 00:05:01,760
vēlas mainīt oriģinālu
vērtības masīvs.

86
00:05:01,760 --> 00:05:05,020
Mēs esam gatavi pāriet
modernizēta vērtības.

87
00:05:05,020 --> 00:05:09,140
>> Tagad mēs nevaram bināro meklēšanu pār
masīvs, kas ir nešķirotas.

88
00:05:09,140 --> 00:05:12,220
Tātad, pieņemsim iegūt šo sakārtoti.

89
00:05:12,220 --> 00:05:17,650
Tagad, ievērosiet, ka veids ir pēdējo divu
parametri int vērtības, kas ir

90
00:05:17,650 --> 00:05:21,110
masīvs, ka mēs esam šķirošana, un int n,
kas ir garums masīva ka

91
00:05:21,110 --> 00:05:22,250
mēs esam šķirošana.

92
00:05:22,250 --> 00:05:24,840
Tātad, šeit mēs vēlamies īstenot
šķirošanas algoritms

93
00:05:24,840 --> 00:05:26,690
kas ir o n brusas.

94
00:05:26,690 --> 00:05:30,560
Jūs varētu izvēlēties burbuļa kārtošanas, atlases
kārtot vai ievietošanas kārtot, vai

95
00:05:30,560 --> 00:05:32,670
kāda cita veida mums nav
redzējuši klasē.

96
00:05:32,670 --> 00:05:36,380
Bet šeit, mēs ejam, lai
izmantot atlases veida.

97
00:05:36,380 --> 00:05:40,030
>> Tātad, mēs esam gatavojas atkārtot
visam blokam.

98
00:05:40,030 --> 00:05:44,360
Nu, šeit mēs redzam, ka mēs esam atkārtojot
mīnus no 0 līdz n 1.

99
00:05:44,360 --> 00:05:45,990
Kāpēc ne visu ceļu līdz pat n?

100
00:05:45,990 --> 00:05:49,320
Nu, ja mēs jau esam sakārtoti pirmais
n mīnus 1 elementi, tad

101
00:05:49,320 --> 00:05:54,420
Ļoti pēdējais elements, kas jau jābūt
pareizajā vietā, lai šķirošanas vairāk

102
00:05:54,420 --> 00:05:56,520
viss masīvs.

103
00:05:56,520 --> 00:05:58,770
>> Tagad atceros, kā atlase
veida darbi.

104
00:05:58,770 --> 00:06:01,950
Mēs ejam, lai iet visam blokam
meklē minimālo vērtību

105
00:06:01,950 --> 00:06:04,480
masīvs un stick ka
sākumā.

106
00:06:04,480 --> 00:06:07,610
Tad mēs esam gatavojas iet pār visu
masīvs atkal meklē otro

107
00:06:07,610 --> 00:06:10,410
mazākais elements, un stick ka
Otrajā pozīcijā

108
00:06:10,410 --> 00:06:12,100
array, un tā tālāk.

109
00:06:12,100 --> 00:06:14,330
Tāpēc, ka tas, ko tas dara.

110
00:06:14,330 --> 00:06:17,290
>> Lūk, mēs redzam, ka mēs esam
nosakot pašreizējo minimālo

111
00:06:17,290 --> 00:06:20,030
vērtība i-indeksu.

112
00:06:20,030 --> 00:06:23,160
Tātad uz pirmā atkārtojuma, mēs ejam
apsvērt minimālā vērtība būtu

113
00:06:23,160 --> 00:06:25,030
sākums mūsu masīvs.

114
00:06:25,030 --> 00:06:28,500
Tad mēs spēsim atkārtot vairāk
pārējā masīva, pārbaudes, lai

115
00:06:28,500 --> 00:06:31,870
redzētu, vai ir kādi elementi mazāks nekā
viens, ka mēs šobrīd esam

116
00:06:31,870 --> 00:06:33,900
ņemot vērā minimumu.

117
00:06:33,900 --> 00:06:38,840
>> Tātad šeit, vērtības J plus viens - tas ir
mazāk, nekā tas, ko mēs pašlaik

118
00:06:38,840 --> 00:06:40,380
ņemot vērā minimumu.

119
00:06:40,380 --> 00:06:42,940
Tad mēs ejam atjaunināt ko
mēs domājam, ir minimums, lai

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

121
00:06:44,640 --> 00:06:48,540
Tātad, darīt pāri visam blokam,
un pēc tam, lai cilpa, minimālo

122
00:06:48,540 --> 00:06:53,160
jābūt vismaz elements no
i-th pozīciju masīvā.

123
00:06:53,160 --> 00:06:57,350
>> Pēc tam, kad mēs esam, ka mēs varam mijmaiņas
minimālā vērtība uz i-tajā pozīcijā

124
00:06:57,350 --> 00:06:58,230
masīvā.

125
00:06:58,230 --> 00:07:00,130
Tāpēc tas ir tikai standarta swap.

126
00:07:00,130 --> 00:07:03,940
Mēs uzglabāt pagaidu vērtības -
i-tā vērtība masīvs -

127
00:07:03,940 --> 00:07:08,460
laiž i-vērtības masīvā
minimālā vērtība, kas pieder tur,

128
00:07:08,460 --> 00:07:13,580
un pēc tam uzglabāt atpakaļ, kad
current minimālā vērtība, ko izmanto, lai būtu

129
00:07:13,580 --> 00:07:16,460
i-tā vērtība masīvs, tāpēc
ka mums nav zaudēt to.

130
00:07:16,460 --> 00:07:20,510
>> Tāpēc, ka turpinās
nākamais atkārtojuma.

131
00:07:20,510 --> 00:07:23,480
Mēs sākt meklēt otro
minimālā vērtība un ievietojiet kas stājas

132
00:07:23,480 --> 00:07:24,590
otro pozīciju.

133
00:07:24,590 --> 00:07:27,440
Trešajā atkārtojuma, mēs meklējam
Trešais minimālā vērtība un ievietot

134
00:07:27,440 --> 00:07:31,550
ka uz trešo pozīciju, un tā
līdz brīdim, kad mums ir sakārtoti masīvs.

135
00:07:31,550 --> 00:07:33,820
Mans vārds ir Rob, un šī
bija izvēle kārtošanas.

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