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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Hæ, ég er Rob.

3
00:00:15,010 --> 00:00:16,790
Hvernig eigum við að ráða tvöfaldur leit?

4
00:00:16,790 --> 00:00:18,770
Skulum finna út.

5
00:00:18,770 --> 00:00:23,400
Svo, athugið að leitina við erum að fara
að hrinda í framkvæmd í undirmöppum.

6
00:00:23,400 --> 00:00:27,470
Þú gætir líka innleiða tvöfaldur leit
iteratively, þannig að ef þú gerðir það,

7
00:00:27,470 --> 00:00:29,280
það er fullkomlega í lagi.

8
00:00:29,280 --> 00:00:32,820
>> Nú fyrst skulum við muna hvað
breytur til að leit er ætlað að vera.

9
00:00:32,820 --> 00:00:36,120
Hér sjáum við INT gildi, sem er
ætlast til að vera gildið sem notandinn er

10
00:00:36,120 --> 00:00:37,320
leita að.

11
00:00:37,320 --> 00:00:40,800
Sjáum við int gildi array, sem
er fylki sem við erum

12
00:00:40,800 --> 00:00:42,520
leita að gildi.

13
00:00:42,520 --> 00:00:45,602
Og við sjáum int n, sem er
lengd fylkisins okkar.

14
00:00:45,602 --> 00:00:47,410
>> Nú, fyrsta sem fyrst.

15
00:00:47,410 --> 00:00:51,350
Við athuga hvort n jafngildir 0, í
því tilviki sem við return false.

16
00:00:51,350 --> 00:00:54,770
Það er bara að segja ef við höfum tóm
array, gildi er greinilega ekki í

17
00:00:54,770 --> 00:00:57,860
tómt array, svo við getum skila falskur.

18
00:00:57,860 --> 00:01:01,250
>> Nú viljum við í raun að gera tvöfaldur
leita hluti af tvöfaldur leit.

19
00:01:01,250 --> 00:01:04,780
Svo viljum við að finna miðju
þáttur í þessu fylki.

20
00:01:04,780 --> 00:01:09,130
Hér segjum við miðja jafngildir n skipt
um 2, frá því um miðja þátturinn er

21
00:01:09,130 --> 00:01:12,240
fara til vera the lengd
array okkar deilt með 2.

22
00:01:12,240 --> 00:01:15,040
Nú við erum að fara að athuga hvort að
miðja þáttur jafnt gildi við séum

23
00:01:15,040 --> 00:01:16,160
leita að.

24
00:01:16,160 --> 00:01:21,030
Þannig að ef gildi miðja jafnt gildi, við
getur skilað satt þar fundum við

25
00:01:21,030 --> 00:01:22,810
gildi í array okkar.

26
00:01:22,810 --> 00:01:26,380
>> En ef það var ekki satt, nú
við þurfum að gera endurkvæma

27
00:01:26,380 --> 00:01:27,840
skref af tvöfaldur leit.

28
00:01:27,840 --> 00:01:30,450
Við þurfum að leita annað hvort til
vinstri fylkisins eða til

29
00:01:30,450 --> 00:01:32,320
miðja fylking.

30
00:01:32,320 --> 00:01:39,280
Svo hér, segjum við ef gildin á miðjunni er
minna en gildi, sem þýðir að verðmæti

31
00:01:39,280 --> 00:01:41,350
var meiri en um miðja
í fylkinu.

32
00:01:41,350 --> 00:01:45,790
Þannig að gildi verður að vera til hægri á
þáttur sem við horfði bara á.

33
00:01:45,790 --> 00:01:48,090
>> Svo hér erum við að fara að
leita í undirmöppum.

34
00:01:48,090 --> 00:01:50,320
Og við munum líta á það sem við erum að brottför
á því á sekúndu.

35
00:01:50,320 --> 00:01:53,440
En við erum að fara að leita að því
rétt af miðjum frumefni.

36
00:01:53,440 --> 00:01:57,710
Og í öðrum tilvikum, sem þýðir að
gildi var minna en the miðja af the

37
00:01:57,710 --> 00:02:00,660
array, og þannig að við ætlum
að leita til vinstri.

38
00:02:00,660 --> 00:02:03,520
Nú, vinstri er að fara að vera
svolítið auðveldara að líta á.

39
00:02:03,520 --> 00:02:07,770
Svo sjáum við hér að við erum endurkvæmt
starf leita þar sem fyrsta

40
00:02:07,770 --> 00:02:10,120
rifrildi er, aftur, gildi
við erum að leita yfir.

41
00:02:10,120 --> 00:02:14,970
Seinni rök er að fara að vera
array sem við vorum að leita á.

42
00:02:14,970 --> 00:02:17,090
Og síðasti þátturinn er nú miðja.

43
00:02:17,090 --> 00:02:21,650
Muna síðustu breytu er int okkar
n, þannig að það er lengd array okkar.

44
00:02:21,650 --> 00:02:25,310
>> Í endurkvæma hringja til að leita, við erum
nú að segja að við lengd

45
00:02:25,310 --> 00:02:27,230
array er miðja.

46
00:02:27,230 --> 00:02:32,900
Svo, ef array okkar var stærð 20 og við
leita í vísitölu 10, þar miðja er

47
00:02:32,900 --> 00:02:36,930
20 deilt með 2, sem þýðir að við erum
liggur 10 sem ný

48
00:02:36,930 --> 00:02:38,300
lengd array okkar.

49
00:02:38,300 --> 00:02:41,910
Mundu að þegar þú ert með array
lengd 10, sem þýðir að í gildi

50
00:02:41,910 --> 00:02:45,450
þættir eru í vísitölunum 0 til 9.

51
00:02:45,450 --> 00:02:50,120
Þannig að þetta er einmitt það sem við viljum
tilgreina uppfærð array okkar - vinstri

52
00:02:50,120 --> 00:02:53,010
array frá miðju frumefni.

53
00:02:53,010 --> 00:02:55,710
>> Svo, að leita til hægri er
svolítið erfiðara.

54
00:02:55,710 --> 00:03:00,170
Nú fyrst skulum við íhuga lengd
í fylkinu til hægri á

55
00:03:00,170 --> 00:03:01,240
miðja þáttur.

56
00:03:01,240 --> 00:03:08,390
Þannig að ef array okkar var af stærðinni N, þá er
Ný fylking mun vera af stærð n mínus

57
00:03:08,390 --> 00:03:10,140
miðja mínus 1.

58
00:03:10,140 --> 00:03:12,530
Svo, við skulum hugsa um n mínus miðju.

59
00:03:12,530 --> 00:03:18,710
>> Aftur, ef array voru af stærð 20 og
við deilum með 2 til að fá miðju,

60
00:03:18,710 --> 00:03:23,540
svo miðju er 10, þá n mínus miðja
er að fara að gefa okkur 10, svo 10

61
00:03:23,540 --> 00:03:25,330
þættir til hægri miðju.

62
00:03:25,330 --> 00:03:27,780
En við höfum líka þessa mínus
1, þar sem við viljum ekki að

63
00:03:27,780 --> 00:03:29,700
fela miðju sjálft.

64
00:03:29,700 --> 00:03:34,190
Svo n mínus miðja mínus 1 gefur okkur
heildarfjöldi staka til hægri

65
00:03:34,190 --> 00:03:36,800
af miðjum vísitölu í array.

66
00:03:36,800 --> 00:03:41,870
>> Nú hér, muna að miðja
breytu er gildi array.

67
00:03:41,870 --> 00:03:46,180
Svo hér erum við að standast
uppfærð gildi array.

68
00:03:46,180 --> 00:03:50,930
Þetta gildi auk miðja plús 1 er
í raun að segja endurkvæmt kalla

69
00:03:50,930 --> 00:03:56,460
leit, liggur í nýju fylki, þar sem
að nýja array byrjar í miðju

70
00:03:56,460 --> 00:03:59,370
plús einn af upprunalegu gildi okkar fylki.

71
00:03:59,370 --> 00:04:05,400
>> Varamaður setningafræði fyrir það, nú þegar
þú hefur byrjað að sjá ábendingum, er

72
00:04:05,400 --> 00:04:10,170
merkið gildi miðja auk 1.

73
00:04:10,170 --> 00:04:17,149
Svo, grípa veffang miðjunni
plús einn þáttur í gildi.

74
00:04:17,149 --> 00:04:23,690
>> Nú, ef þú værir ekki ánægð
breyta fjölda svona, þú

75
00:04:23,690 --> 00:04:28,900
gæti einnig hafa innleitt þetta með
endurkvæma hjálpar virka, þar

76
00:04:28,900 --> 00:04:31,680
sem hjálpar virka tekur
fleiri rök.

77
00:04:31,680 --> 00:04:36,610
Svo í stað þess að taka bara gildi,
array, og the stærð af the array,

78
00:04:36,610 --> 00:04:42,315
sem hjálpar virka gæti tekið meira
rök, þar á meðal lægri vísitölu

79
00:04:42,315 --> 00:04:45,280
að þú myndir hugsa um í array
og efri vísitölu sem þér þykir vænt

80
00:04:45,280 --> 00:04:46,300
um fylki.

81
00:04:46,300 --> 00:04:49,770
>> Og svo halda utan um bæði lægri
vísitölu og efri vísitölu, þú gerir ekki

82
00:04:49,770 --> 00:04:52,780
þarf að alltaf breyta
upprunalegt horf array.

83
00:04:52,780 --> 00:04:56,390
Þú getur bara haldið áfram að
nota gildin array.

84
00:04:56,390 --> 00:04:59,540
En hér, taka við þurfum ekki hjálpar
virka svo lengi sem við erum

85
00:04:59,540 --> 00:05:01,760
tilbúnir til að breyta upprunalegu
gildi array.

86
00:05:01,760 --> 00:05:05,020
Við erum tilbúnir til að fara í
uppfærða gildi.

87
00:05:05,020 --> 00:05:09,140
>> Nú getum við ekki tvöfaldur leit yfir
fylki sem er óflokkað.

88
00:05:09,140 --> 00:05:12,220
Svo skulum við fá þessa tegund út.

89
00:05:12,220 --> 00:05:17,650
Nú, taka þessi tegund er framhjá tveimur
breytur int gildi, sem er

90
00:05:17,650 --> 00:05:21,110
array sem við erum að flokka, og INT n,
sem er lengd fylkingu sem

91
00:05:21,110 --> 00:05:22,250
við erum að flokka.

92
00:05:22,250 --> 00:05:24,840
Svo, hér við viljum að innleiða
á að flokka reiknirit

93
00:05:24,840 --> 00:05:26,690
sem er o af n í öðru veldi.

94
00:05:26,690 --> 00:05:30,560
Þú gætir valið kúla tagi, úrval
tegund, eða innsetning tegund, eða

95
00:05:30,560 --> 00:05:32,670
einhver önnur tegund sem við höfum ekki
séð í bekknum.

96
00:05:32,670 --> 00:05:36,380
En hér erum við að fara að
nota val konar.

97
00:05:36,380 --> 00:05:40,030
>> Svo erum við að fara að iterate
yfir allt array.

98
00:05:40,030 --> 00:05:44,360
Jæja, hér sjáum við að við erum iterating
frá 0 til N mínus 1.

99
00:05:44,360 --> 00:05:45,990
Af hverju ekki alla leið upp til n?

100
00:05:45,990 --> 00:05:49,320
Jæja, ef við höfum þegar raðað fyrst
n mínus 1 atriði, þá

101
00:05:49,320 --> 00:05:54,420
mjög síðustu þáttur hvað verður þegar að vera
á réttan stað, þannig að flokkun á

102
00:05:54,420 --> 00:05:56,520
Fylkið.

103
00:05:56,520 --> 00:05:58,770
>> Nú, muna hvernig val
Raða virkar.

104
00:05:58,770 --> 00:06:01,950
Við ætlum að fara yfir allt array
að leita að lægsta gildi í

105
00:06:01,950 --> 00:06:04,480
array og stafur sem
í upphafi.

106
00:06:04,480 --> 00:06:07,610
Svo ætlum við að fara yfir allt
array aftur að leita fyrir þá síðari

107
00:06:07,610 --> 00:06:10,410
Minnsta þáttur, og stafur sem
í annarri stöðu í

108
00:06:10,410 --> 00:06:12,100
array, og svo framvegis.

109
00:06:12,100 --> 00:06:14,330
Svo, það er það sem þetta er að gera.

110
00:06:14,330 --> 00:06:17,290
>> Hér erum við að sjá að við erum
setja núverandi lágmarki

111
00:06:17,290 --> 00:06:20,030
gildi til i-ta vísitölunni.

112
00:06:20,030 --> 00:06:23,160
Svo á fyrsta endurtekning, við erum að fara
til að fjalla um lágmarks gildi að vera

113
00:06:23,160 --> 00:06:25,030
byrjunin á fjölda okkar.

114
00:06:25,030 --> 00:06:28,500
Þá erum við að fara að iterate yfir
Afgangurinn af array, stöðva til

115
00:06:28,500 --> 00:06:31,870
sjá hvort einhver atriði minni en
sá sem við erum nú

116
00:06:31,870 --> 00:06:33,900
miðað lágmarki.

117
00:06:33,900 --> 00:06:38,840
>> Svo hér, gildi j plús einn - það er
minna en það sem við erum nú

118
00:06:38,840 --> 00:06:40,380
miðað lágmarki.

119
00:06:40,380 --> 00:06:42,940
Þá erum við að fara að uppfæra það
við höldum að sé lágmark að

120
00:06:42,940 --> 00:06:44,640
Vísitala J auk 1.

121
00:06:44,640 --> 00:06:48,540
Svo, gera það á öllu fylkinu,
og eftir þetta fyrir lykkju, lágmarks

122
00:06:48,540 --> 00:06:53,160
ætti að vera lágmarks þáttur frá
i-th staða í array.

123
00:06:53,160 --> 00:06:57,350
>> Þegar við höfum það getum við skipti á
Lægsta gildi í i-ta stöðu

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

125
00:06:58,230 --> 00:07:00,130
Svo er þetta bara staðall skipti.

126
00:07:00,130 --> 00:07:03,940
Við geymum í tímabundinni gildi -
i-th gildi í fylkinu -

127
00:07:03,940 --> 00:07:08,460
setja í i-ta gildi í fylkinu sem
lágmarks gildi sem tilheyrir þar,

128
00:07:08,460 --> 00:07:13,580
og síðan geyma aftur í þar sem
Núverandi lágmarksgildi notað til að vera

129
00:07:13,580 --> 00:07:16,460
I-th gildi í fylkinu, svo
að við vildum ekki missa það.

130
00:07:16,460 --> 00:07:20,510
>> Svo, sem heldur áfram á
næsta endurtekning.

131
00:07:20,510 --> 00:07:23,480
Við munum byrja að leita fyrir þá síðari
lágmarks gildi og setja það inn í

132
00:07:23,480 --> 00:07:24,590
seinni stöðuna.

133
00:07:24,590 --> 00:07:27,440
Á þriðja endurtekning, munum við leita
þriðja lágmarks gildi og settu

134
00:07:27,440 --> 00:07:31,550
sem í þriðju stöðuna sem, og svo
á þar til við höfum raðað fylki.

135
00:07:31,550 --> 00:07:33,820
Mitt nafn er Rob, og þetta
var val konar.

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