1
00:00:00,000 --> 00:00:08,532
>> [Tónlist spila]

2
00:00:08,532 --> 00:00:12,060
>> ZAMYLA CHAN: The fyrstur hlutur þú might
tilkynning um að finna er að við nú þegar

3
00:00:12,060 --> 00:00:13,450
hafa númerið skrifað fyrir okkur.

4
00:00:13,450 --> 00:00:15,160
Þetta er kallað dreifing númer.

5
00:00:15,160 --> 00:00:18,000
Þannig að við erum ekki bara að skrifa okkar eigin
kóða frá grunni aftur.

6
00:00:18,000 --> 00:00:22,800
Frekar erum við að fylla í tóm
í sumum fyrirliggjandi kóða.

7
00:00:22,800 --> 00:00:27,790
>> The find.c program hvetja til tölur
að fylla Heysátan, leitar í

8
00:00:27,790 --> 00:00:32,189
Heysátan fyrir notanda lögð nál,
og það gerir þetta með því að kalla tagi og

9
00:00:32,189 --> 00:00:35,590
leit, aðgerðir skilgreindar
í helpers.c.

10
00:00:35,590 --> 00:00:37,670
Svo find.c er skrifað nú þegar.

11
00:00:37,670 --> 00:00:40,770
Starf þitt er að skrifa framreiðslu.

12
00:00:40,770 --> 00:00:41,870
>> Og hvað erum við að gera?

13
00:00:41,870 --> 00:00:44,210
Við erum að innleiða tvær aðgerðir.

14
00:00:44,210 --> 00:00:49,030
Leit, sem skilar true ef gildi
er að finna í Heysátan, aftur

15
00:00:49,030 --> 00:00:51,370
false ef gildið er
ekki í Heysátan.

16
00:00:51,370 --> 00:00:57,990
Og þá erum við líka að innleiða einhverskonar
Hvaða tegund array sem heitir gildi.

17
00:00:57,990 --> 00:00:59,960
>> Svo skulum takast leit.

18
00:00:59,960 --> 00:01:04,560
Leit er nú útfærð sem
línuleg leit, en þú getur gert mikið

19
00:01:04,560 --> 00:01:05,550
betur en það.

20
00:01:05,550 --> 00:01:09,910
Línuleg leit er framkvæmd í O
af n tíma, sem er alveg hægt.

21
00:01:09,910 --> 00:01:13,850
Þrátt fyrir að það getur leitað
Allir lista gefið.

22
00:01:13,850 --> 00:01:20,130
Starf þitt er að innleiða tvöfaldur leit,
sem hefur rekið sinn o frá log n.

23
00:01:20,130 --> 00:01:21,130
Það er ansi hratt.

24
00:01:21,130 --> 00:01:23,170
>> En það er áskilnaður.

25
00:01:23,170 --> 00:01:27,600
Tvíundarleit getur aðeins leitað
með fyrirfram raðað lista.

26
00:01:27,600 --> 00:01:30,370
Hvers vegna er það?

27
00:01:30,370 --> 00:01:32,620
>> Jæja við skulum líta á dæmi.

28
00:01:32,620 --> 00:01:36,280
Fá array af gildum, Heysátan,
við erum að fara að horfa

29
00:01:36,280 --> 00:01:37,130
að nál.

30
00:01:37,130 --> 00:01:40,460
Og í þessu dæmi,
heiltölunni þrjú.

31
00:01:40,460 --> 00:01:44,130
Leiðin að Tvíundarleit virkar er að
við saman á miðju gildi

32
00:01:44,130 --> 00:01:48,370
array nálinni mikið eins og hvernig
opnað símaskránni að miðju

33
00:01:48,370 --> 00:01:50,660
síðu í viku núll.

34
00:01:50,660 --> 00:01:54,650
>> Svo eftir að bera saman miðju gildi til
nálina, getur þú henda annaðhvort

35
00:01:54,650 --> 00:01:58,530
vinstri eða hægri helminginn af array
með því að herða mörk þín.

36
00:01:58,530 --> 00:02:03,390
Í þessu tilviki, þar sem þrjú, nál okkar,
er minna en 10, miðju gildi,

37
00:02:03,390 --> 00:02:05,990
rétt bundið getur lækkað.

38
00:02:05,990 --> 00:02:08,400
En að reyna að gera mörk þínum
eins þétt og mögulegt er.

39
00:02:08,400 --> 00:02:11,630
Ef miðju gildið ekki nálina,
þá veistu að þú þarft ekki að

40
00:02:11,630 --> 00:02:13,010
fela það í leitinni.

41
00:02:13,010 --> 00:02:17,310
Svo þú ert rétt bundið getur herða
Leita mörk bara örlítið aðeins meira,

42
00:02:17,310 --> 00:02:21,770
og svo framvegis og svo framvegis þar til
þú finnur nálinni þína.

43
00:02:21,770 --> 00:02:23,480
>> Svo hvað þýðir sauðakóðanum líta út?

44
00:02:23,480 --> 00:02:28,420
Vel á meðan við erum enn að leita gegnum
lista og enn hafa þætti til

45
00:02:28,420 --> 00:02:33,690
líta í, taka við miðjum listanum,
og bera saman þessi miðju gildi til

46
00:02:33,690 --> 00:02:34,950
nál okkar.

47
00:02:34,950 --> 00:02:37,310
Ef þeir eru jafnir, þá þýðir að við höfum
fann nálina og við getum

48
00:02:37,310 --> 00:02:38,990
return true.

49
00:02:38,990 --> 00:02:42,870
>> Að öðrum kosti, ef nálin er minna en
miðju gildi, þá þýðir það að við

50
00:02:42,870 --> 00:02:47,280
getur fleygt hægri helminginn, og bara
leita á vinstri hlið af the array.

51
00:02:47,280 --> 00:02:51,090
Annars verður við leit að
hægra megin í fylkinu.

52
00:02:51,090 --> 00:02:54,410
Og í lok, ef þú ert ekki með neina
fleiri þættir vinstri til að leita, en þú

53
00:02:54,410 --> 00:02:58,050
hef ekki fundið nál þína enn, þá þú
return false því nálin

54
00:02:58,050 --> 00:03:01,890
örugglega er ekki í Heysátan.

55
00:03:01,890 --> 00:03:05,270
>> Nú snyrtilegur hlutur óður í this sauðakóðanum
í tvöfaldur leit er að það getur verið

56
00:03:05,270 --> 00:03:09,940
túlka sem annað hvort endurtekningu
eða endurkvæma framkvæmd.

57
00:03:09,940 --> 00:03:13,810
Svo það væri endurkvæma ef þú kallaðir
leit virka innan leit

58
00:03:13,810 --> 00:03:17,350
virka á hvorum helmingi fylkisins.

59
00:03:17,350 --> 00:03:21,030
Við munum ná endurkvæmni svolítið síðar í
Auðvitað, en veit að það er

60
00:03:21,030 --> 00:03:24,190
kostur ef þú vilt reyna.

61
00:03:24,190 --> 00:03:26,030
>> Nú skulum líta á tegund.

62
00:03:26,030 --> 00:03:30,750
Raða tekur við fylki og heiltölunni
n, sem er á stærð fylkisins.

63
00:03:30,750 --> 00:03:34,030
Nú eru ýmsar mismunandi gerðir
nokkurs konar, og þú getur litið á nokkur

64
00:03:34,030 --> 00:03:36,370
stuttbuxur fyrir kynningum og skýringum.

65
00:03:36,370 --> 00:03:39,580
Afrakstur gerð til okkar
Raða virka er ógilt.

66
00:03:39,580 --> 00:03:43,580
Svo það þýðir að við erum ekki að fara
að skila öllum array af tagi.

67
00:03:43,580 --> 00:03:48,140
Við erum í raun að fara að breyta mjög
array sem var samþykkt í okkur.

68
00:03:48,140 --> 00:03:52,290
>> Og það er hægt vegna þess að fylki eru
samþykkt með tilvísun í C. Nú munum við

69
00:03:52,290 --> 00:03:55,290
sjá meira um þetta síðar, en
Meginmunur milli brottför

70
00:03:55,290 --> 00:03:59,340
í eitthvað eins heiltala og brottför
í fylki, er að þegar þú

71
00:03:59,340 --> 00:04:03,490
fara í heiltala, C er bara að fara að
gera afrit af þeim heiltölu og standast

72
00:04:03,490 --> 00:04:04,450
það við aðgerðina.

73
00:04:04,450 --> 00:04:08,530
Upphaflegt breytu verður ekki breytt
Þegar aðgerð er lokið.

74
00:04:08,530 --> 00:04:12,480
Með fjölda, á hinn bóginn, er það
ekki að fara að gera afrit, og þú munt

75
00:04:12,480 --> 00:04:17,910
raun verið að breyta
mjög array sjálft.

76
00:04:17,910 --> 00:04:21,269
>> Svo er ein tegund af tagi
val tagi.

77
00:04:21,269 --> 00:04:24,750
Val Raða virkar með því að byrja á
upphaf, og þá þú iterate

78
00:04:24,750 --> 00:04:26,820
yfir og finna minnstu frumefni.

79
00:04:26,820 --> 00:04:30,710
Og þá þú skipta að minnsta
þáttur við þá fyrstu.

80
00:04:30,710 --> 00:04:34,360
Og þá þú fara í annað frumefni
, Finna næsta minnstu

81
00:04:34,360 --> 00:04:38,320
þáttur, og þá skipta að með
Annað þáttur í array þar

82
00:04:38,320 --> 00:04:41,100
Fyrsti þátturinn er þegar raðað.

83
00:04:41,100 --> 00:04:45,370
Og svo þá sem þú heldur áfram að sérhver
þáttur í að greina minnstu

84
00:04:45,370 --> 00:04:47,690
gildi og skipta um það út.

85
00:04:47,690 --> 00:04:53,460
>> Ég jafngildir 0, the mjög fyrstur þáttur
til n mínus 1, ætlar þú að fara að bera saman

86
00:04:53,460 --> 00:04:57,820
hvert næsta gildi eftir það og finna
vísitölu lágmarks gildi.

87
00:04:57,820 --> 00:05:02,520
Þegar þú hefur fundið lágmarks gildi vísitölu,
þú getur skipti að verðmæti array

88
00:05:02,520 --> 00:05:05,930
lágmarki og array I.

89
00:05:05,930 --> 00:05:09,760
>> Önnur gerð af tagi sem þú getur
hrinda í framkvæmd er kúla tegund.

90
00:05:09,760 --> 00:05:14,380
Svo kúla raða iterates yfir listanum
bera samliggjandi þætti og

91
00:05:14,380 --> 00:05:17,720
skipta þau atriði sem
eru í rangri röð.

92
00:05:17,720 --> 00:05:22,380
Og þetta leið, stærsti þátturinn
mun kúla til enda.

93
00:05:22,380 --> 00:05:28,070
Og listinn er raðað einu sinni ekki meira
þættir hafa verið skipti.

94
00:05:28,070 --> 00:05:31,920
>> Þannig að þeir eru tvö dæmi um tegund
reiknirit sem hægt er að hrinda í framkvæmd fyrir

95
00:05:31,920 --> 00:05:33,230
að finna program.

96
00:05:33,230 --> 00:05:37,350
Þegar þú hefur lokið að raða, og þú hefur
gert leit, þú ert búinn.

97
00:05:37,350 --> 00:05:39,720
Mitt nafn er Zamyla, og þetta er CS50.

98
00:05:39,720 --> 00:05:46,987
>> [Tónlist spila]