1
00:00:00,000 --> 00:00:09,560

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA Chan: Ang unang bagay na maaari mong
paunawa tungkol sa find ay na namin na

3
00:00:13,120 --> 00:00:14,520
na-code na isinulat para sa amin.

4
00:00:14,520 --> 00:00:16,219
Ito ay tinatawag na code sa pamamahagi.

5
00:00:16,219 --> 00:00:19,060
Kaya hindi lang kami ay sumusulat ating sariling
code mula sa simula ngayon.

6
00:00:19,060 --> 00:00:23,870
Sa halip, kami ay pagpuno sa voids
sa ilang mga pre-umiiral na code.

7
00:00:23,870 --> 00:00:28,860
>> Ang programa ng find.c prompt para sa mga numero ng
upang punan ang mandala ng dayami, ang mga paghahanap ang

8
00:00:28,860 --> 00:00:33,260
mandala ng dayami para sa isang isinumite ng gumagamit karayom,
at gagawin nito ito sa pamamagitan ng pagtawag uri at

9
00:00:33,260 --> 00:00:36,660
paghahanap, mga pag-andar na tinukoy
sa helpers.c.

10
00:00:36,660 --> 00:00:38,740
Kaya find.c ay nakasulat na.

11
00:00:38,740 --> 00:00:41,840
Ang iyong trabaho ay sumulat ng Katulong.

12
00:00:41,840 --> 00:00:42,940
>> Kaya kung ano ang ginagawa namin?

13
00:00:42,940 --> 00:00:45,270
Kami ay pagpapatupad ng dalawang mga pag-andar.

14
00:00:45,270 --> 00:00:50,110
Paghahanap, na nagbabalik totoo kung ang isang halaga
ay natagpuan sa mandala ng dayami, bumabalik

15
00:00:50,110 --> 00:00:52,430
hindi totoo kung ang halaga ay
wala sa mandala ng dayami.

16
00:00:52,430 --> 00:00:59,060
At pagkatapos kami ay pagpapatupad ring uri,
aling uri ang array na tinatawag na mga halaga.

17
00:00:59,060 --> 00:01:01,120
Kaya pagharap sa isang bagay ng paghahanap ipaalam.

18
00:01:01,120 --> 00:01:04,550
>> Search ay kasalukuyang ipinapatupad
bilang isang linear paghahanap.

19
00:01:04,550 --> 00:01:06,620
Ngunit maaari mong gawin magkano ang mas mahusay kaysa sa na.

20
00:01:06,620 --> 00:01:11,610
De-sa paghahanap ay ipinapatupad sa Oh ng n
oras, na kung saan ay masyadong mabagal, kahit na ito

21
00:01:11,610 --> 00:01:14,920
Maaaring maghanap anumang ibinigay na listahan dito.

22
00:01:14,920 --> 00:01:21,190
Ang iyong trabaho ay ang ipatupad ang binary paghahanap,
kung saan tumakbo na oras O ng log n.

23
00:01:21,190 --> 00:01:22,200
Iyon ay medyo mabilis.

24
00:01:22,200 --> 00:01:24,240
>> Subalit mayroong isang tadhana.

25
00:01:24,240 --> 00:01:28,910
Maaari lamang maghanap ng binary paghahanap
sa pamamagitan ng pre-pinagsunod-sunod ng mga listahan.

26
00:01:28,910 --> 00:01:31,450
Bakit na?

27
00:01:31,450 --> 00:01:33,690
Well, tingnan natin ang isang halimbawa ipaalam.

28
00:01:33,690 --> 00:01:37,350
Given isang array ng mga halaga, ang mandala ng dayami,
kami ay pagpunta sa tumitingin

29
00:01:37,350 --> 00:01:41,510
para sa isang karayom, at sa ganitong
Halimbawa, ang integer 3.

30
00:01:41,510 --> 00:01:45,220
>> Ang paraan na gumagana ang binary paghahanap ay na
ihambing namin ang gitnang halaga ng

31
00:01:45,220 --> 00:01:49,430
ang array sa karayom, halos tulad ng kung paano
binuksan namin ang isang libro ng telepono sa gitna

32
00:01:49,430 --> 00:01:51,720
pahina sa Linggo 0.

33
00:01:51,720 --> 00:01:55,710
Kaya pagkatapos ng paghahambing sa gitna ng halaga sa
ang karayom, maaari mong itapon ang alinman sa

34
00:01:55,710 --> 00:01:59,620
kaliwa o kanan kalahati ng array
sa pamamagitan ng apreta ang iyong mga hanggahan.

35
00:01:59,620 --> 00:02:04,450
Sa kasong ito, dahil 3, ang aming karayom, ay
mas mababa sa 10, sa gitna halaga, ang

36
00:02:04,450 --> 00:02:07,060
maaaring bumaba karapatan tumalbog.

37
00:02:07,060 --> 00:02:09,470
>> Ngunit subukan upang gawin ang iyong mga hanggahan
bilang masikip hangga't maaari.

38
00:02:09,470 --> 00:02:12,690
Kung sa gitna halaga ay hindi ang karayom,
pagkatapos ay alam mo na hindi mo kailangang

39
00:02:12,690 --> 00:02:14,070
isama ito sa iyong paghahanap.

40
00:02:14,070 --> 00:02:18,390
Kaya masaklawan ang iyong karapatan Maaari higpitan ang
hanggahan sa paghahanap lamang ng isang maliit na maliit bit higit pa,

41
00:02:18,390 --> 00:02:22,840
at iba pa at iba pa, hanggang sa
mo mahanap ang iyong mga karayom.

42
00:02:22,840 --> 00:02:24,580
>> Kaya ano ang ginagawa ng palsipikado
code ganito ang hitsura?

43
00:02:24,580 --> 00:02:28,980
Well, habang kami ay pa rin ng pagtingin sa
ang listahan at mayroon pa rin

44
00:02:28,980 --> 00:02:33,540
elemento upang tumingin sa, tumagal kami sa gitna
ng mga listahan at ihambing na

45
00:02:33,540 --> 00:02:36,020
gitna ng halaga sa aming mga karayom.

46
00:02:36,020 --> 00:02:38,380
Kung hindi nila ito katumbas, pagkatapos ay nangangahulugan na hindi namin
natagpuan ang karayom, at kaya namin

47
00:02:38,380 --> 00:02:40,160
nagbabalik ng tunay.

48
00:02:40,160 --> 00:02:43,940
>> Kung hindi man, kung ang karayom ​​ay mas mababa sa
sa gitna halaga, pagkatapos ito ay nangangahulugan na namin

49
00:02:43,940 --> 00:02:48,350
Maaari itapon ang mga karapatan at kalahati lamang
maghanap sa kaliwang bahagi ng array.

50
00:02:48,350 --> 00:02:51,860
Kung hindi man, gagamitin namin maghanap sa
kanang bahagi ng array.

51
00:02:51,860 --> 00:02:55,470
At sa dulo, kung wala kang anumang
higit pang mga elemento sa kaliwa upang maghanap ngunit ikaw

52
00:02:55,470 --> 00:02:58,030
hindi pa natagpuan ang iyong mga karayom,
pagkatapos ay bumalik ka ng hindi totoo.

53
00:02:58,030 --> 00:03:02,960
Dahil ang mga karayom ​​Talagang
ay wala sa mandala ng dayami.

54
00:03:02,960 --> 00:03:06,200
>> Ngayon, isa kapong baka bagay tungkol sa ito palsipikado
code sa binary paghahanap ay na kaya nito

55
00:03:06,200 --> 00:03:11,000
mangahulugan bilang alinman sa isang umuulit
o recursive pagpapatupad.

56
00:03:11,000 --> 00:03:14,900
Kaya magiging recursive kung tinatawag mo
ang pag-andar ng paghahanap sa loob ang paghahanap

57
00:03:14,900 --> 00:03:18,400
gumana sa alinman sa kalahati ng array.

58
00:03:18,400 --> 00:03:20,750
Magpapadala kami ng kaunti masakop ang recursion
mamaya sa kurso.

59
00:03:20,750 --> 00:03:23,210
Ngunit alam na ito ay isang opsyon
kung nais mong subukan.

60
00:03:23,210 --> 00:03:24,460