1 00:00:00,000 --> 00:00:08,532 >> [MUSIC nagpe-play] 2 00:00:08,532 --> 00:00:12,060 >> ZAMYLA Chan: Ang unang bagay na maaari mong paunawa tungkol sa find ay na namin na 3 00:00:12,060 --> 00:00:13,450 na-code na isinulat para sa amin. 4 00:00:13,450 --> 00:00:15,160 Ito ay tinatawag na code sa pamamahagi. 5 00:00:15,160 --> 00:00:18,000 Kaya hindi lang kami ay sumusulat ating sariling code mula sa simula ngayon. 6 00:00:18,000 --> 00:00:22,800 Sa halip, kami ay pagpuno sa voids sa ilang mga pre-umiiral na code. 7 00:00:22,800 --> 00:00:27,790 >> Ang programa ng find.c prompt para sa mga numero ng upang punan ang mandala ng dayami, ang mga paghahanap ang 8 00:00:27,790 --> 00:00:32,189 mandala ng dayami para sa isang isinumite ng gumagamit karayom, at gagawin nito ito sa pamamagitan ng pagtawag uri at 9 00:00:32,189 --> 00:00:35,590 paghahanap, mga pag-andar na tinukoy sa helpers.c. 10 00:00:35,590 --> 00:00:37,670 Kaya find.c ay nakasulat na. 11 00:00:37,670 --> 00:00:40,770 Ang iyong trabaho ay sumulat ng Katulong. 12 00:00:40,770 --> 00:00:41,870 >> Kaya kung ano ang ginagawa namin? 13 00:00:41,870 --> 00:00:44,210 Kami ay pagpapatupad ng dalawang mga pag-andar. 14 00:00:44,210 --> 00:00:49,030 Paghahanap, na nagbabalik totoo kung ang isang halaga ay natagpuan sa mandala ng dayami, bumabalik 15 00:00:49,030 --> 00:00:51,370 hindi totoo kung ang halaga ay wala sa mandala ng dayami. 16 00:00:51,370 --> 00:00:57,990 At pagkatapos kami ay pagpapatupad ring uri aling uri ang array na tinatawag na mga halaga. 17 00:00:57,990 --> 00:00:59,960 >> Kaya pagharap sa isang bagay ng paghahanap ipaalam. 18 00:00:59,960 --> 00:01:04,560 Search ay kasalukuyang ipinapatupad bilang isang linear na paghahanap, ngunit maaari mong gawin magkano 19 00:01:04,560 --> 00:01:05,550 mas mahusay kaysa sa na. 20 00:01:05,550 --> 00:01:09,910 De-sa paghahanap ay ipinapatupad sa Oh ng n oras, na kung saan ay masyadong mabagal. 21 00:01:09,910 --> 00:01:13,850 Bagaman, maaari itong hanapin anumang mga listahan na ibinigay dito. 22 00:01:13,850 --> 00:01:20,130 Ang iyong trabaho ay ang ipatupad ang binary paghahanap, kung saan tumakbo na oras O ng log n. 23 00:01:20,130 --> 00:01:21,130 Iyon ay medyo mabilis. 24 00:01:21,130 --> 00:01:23,170 >> Subalit mayroong isang tadhana. 25 00:01:23,170 --> 00:01:27,600 Maaari lamang maghanap ng binary paghahanap sa pamamagitan ng pre-pinagsunod-sunod ng mga listahan. 26 00:01:27,600 --> 00:01:30,370 Bakit na? 27 00:01:30,370 --> 00:01:32,620 >> Tingnan natin ang isang halimbawa Well ipaalam. 28 00:01:32,620 --> 00:01:36,280 Given isang array ng mga halaga, ang mandala ng dayami, kami ay pagpunta sa tumitingin 29 00:01:36,280 --> 00:01:37,130 para sa isang karayom. 30 00:01:37,130 --> 00:01:40,460 At sa halimbawang ito, ang integer tatlo. 31 00:01:40,460 --> 00:01:44,130 Ang paraan na gumagana ang binary paghahanap ay na ihambing namin ang gitnang halaga ng 32 00:01:44,130 --> 00:01:48,370 ang array sa karayom, halos tulad ng kung paano binuksan namin ang isang phonebook sa gitna 33 00:01:48,370 --> 00:01:50,660 pahina sa linggo zero. 34 00:01:50,660 --> 00:01:54,650 >> Kaya pagkatapos ng paghahambing sa gitna ng halaga sa ang karayom, maaari mong itapon ang alinman sa 35 00:01:54,650 --> 00:01:58,530 kaliwa o kanan kalahati ng array sa pamamagitan ng apreta ang iyong mga hanggahan. 36 00:01:58,530 --> 00:02:03,390 Sa kasong ito, dahil tatlong, ang aming karayom, Mas mababa sa 10, sa gitna halaga, ang 37 00:02:03,390 --> 00:02:05,990 maaaring bumaba karapatan tumalbog. 38 00:02:05,990 --> 00:02:08,400 Ngunit subukan upang gawin ang iyong mga hanggahan bilang masikip hangga't maaari. 39 00:02:08,400 --> 00:02:11,630 Kung sa gitna halaga ay hindi ang karayom, pagkatapos ay alam mo na hindi mo kailangang 40 00:02:11,630 --> 00:02:13,010 isama ito sa iyong paghahanap. 41 00:02:13,010 --> 00:02:17,310 Kaya ikaw ay kanan nakatali Maaari higpitan ang hanggahan sa paghahanap lamang ng isang maliit na maliit bit higit pa, 42 00:02:17,310 --> 00:02:21,770 at iba pa at iba pa hanggang sa mo mahanap ang iyong mga karayom. 43 00:02:21,770 --> 00:02:23,480 >> Kaya kung ano ang hitsura ng pseudocode tulad? 44 00:02:23,480 --> 00:02:28,420 Well habang pa rin kaming naghahanap sa pamamagitan ng ang listahan at mayroon pa ring mga elemento sa 45 00:02:28,420 --> 00:02:33,690 tumingin sa, tumagal kami sa gitna ng listahan, at ihambing na gitna ng halaga sa 46 00:02:33,690 --> 00:02:34,950 ang aming karayom. 47 00:02:34,950 --> 00:02:37,310 Kung hindi nila ito katumbas, pagkatapos ay nangangahulugan na hindi namin natagpuan ang karayom ​​at kaya namin 48 00:02:37,310 --> 00:02:38,990 nagbabalik ng tunay. 49 00:02:38,990 --> 00:02:42,870 >> Kung hindi man, kung ang karayom ​​ay mas mababa sa sa gitna halaga, pagkatapos ito ay nangangahulugan na namin 50 00:02:42,870 --> 00:02:47,280 Maaari itapon ang mga karapatan kalahati, at lamang maghanap sa kaliwang bahagi ng array. 51 00:02:47,280 --> 00:02:51,090 Kung hindi man, gagamitin namin maghanap sa kanang bahagi ng array. 52 00:02:51,090 --> 00:02:54,410 At sa dulo, kung wala kang anumang higit pang mga elemento sa kaliwa upang maghanap ngunit ikaw 53 00:02:54,410 --> 00:02:58,050 hindi pa natagpuan ang iyong mga karayom, pagkatapos mo bumalik hindi totoo dahil ang karayom 54 00:02:58,050 --> 00:03:01,890 Talagang ay wala sa mandala ng dayami. 55 00:03:01,890 --> 00:03:05,270 >> Ngayon isang kapong baka bagay tungkol sa ito pseudocode sa binary paghahanap ay na maaari itong maging 56 00:03:05,270 --> 00:03:09,940 kahulugan bilang alinman sa isang umuulit o recursive pagpapatupad. 57 00:03:09,940 --> 00:03:13,810 Kaya magiging recursive kung tinatawag mo ang pag-andar ng paghahanap sa loob ang paghahanap 58 00:03:13,810 --> 00:03:17,350 gumana sa alinman sa kalahati ng array. 59 00:03:17,350 --> 00:03:21,030 Tatalakayin namin ang recursion ng kaunti mamaya sa Siyempre, ngunit alam na ito ay isang 60 00:03:21,030 --> 00:03:24,190 opsyong ito kung gusto mong subukan. 61 00:03:24,190 --> 00:03:26,030 >> Ngayon tingnan natin ang uri ipaalam. 62 00:03:26,030 --> 00:03:30,750 Pagbukud-bukurin tumatagal ng isang array at ang integer n, kung saan ay ang laki ng array. 63 00:03:30,750 --> 00:03:34,030 Ngayon may mga iba't-ibang mga iba't ibang mga uri ng mga uri, at maaari kang tumingin sa ilang mga 64 00:03:34,030 --> 00:03:36,370 shorts para sa mga demo at mga paliwanag. 65 00:03:36,370 --> 00:03:39,580 Ang uri ng return para sa aming mga sort function na ay walang bisa. 66 00:03:39,580 --> 00:03:43,580 Kaya ibig sabihin nito ay na hindi namin pagpunta maibalik ang anumang mga array mula sa uri. 67 00:03:43,580 --> 00:03:48,140 Talaga kami ng pagpunta upang baguhin ang napaka array na ay pumasa sa sa amin. 68 00:03:48,140 --> 00:03:52,290 >> At na posible dahil array ay pumasa sa pamamagitan ng sanggunian sa C. Ngayon namin makikita 69 00:03:52,290 --> 00:03:55,290 tingnan ang higit pa tungkol ito sa ibang pagkakataon, ngunit ang mahahalagang pagkakaiba sa pagitan ng nagdaraan 70 00:03:55,290 --> 00:03:59,340 sa isang bagay tulad ng isang integer at nagdaraan sa isang array, ay na kapag nag- 71 00:03:59,340 --> 00:04:03,490 pumasa sa isang integer, C ay pagpunta lamang sa gumawa ng kopya ng na integer at pumasa sa 72 00:04:03,490 --> 00:04:04,450 ito sa function. 73 00:04:04,450 --> 00:04:08,530 Ang orihinal na variable ay hindi mababago sa sandaling ang function ay tapos na. 74 00:04:08,530 --> 00:04:12,480 Gamit ang isang array, sa kabilang banda, ito ay hindi pagpunta sa gumawa ng kopya, at idedetalye mo 75 00:04:12,480 --> 00:04:17,910 talaga mai-e-edit ang napaka mismo ng array. 76 00:04:17,910 --> 00:04:21,269 >> Kaya isang uri ng pag-uuri ay ang uri pagpili. 77 00:04:21,269 --> 00:04:24,750 Nagsisikap ang uri pagpili sa pamamagitan ng simula sa sa simula, at pagkatapos ay umulit sa iyo 78 00:04:24,750 --> 00:04:26,820 sa ibabaw at hanapin ang pinakamaliit na elemento. 79 00:04:26,820 --> 00:04:30,710 At pagkatapos ay magpalit ka na pinakamaliit elemento na may unang isa. 80 00:04:30,710 --> 00:04:34,360 At pagkatapos lumipat ka sa pangalawang elemento , Hanapin ang susunod pinakamaliliit 81 00:04:34,360 --> 00:04:38,320 elemento, at pagkatapos ay magpalit na may mga pangalawang elemento sa array dahil 82 00:04:38,320 --> 00:04:41,100 sa unang elemento ay naka-pinagsunod-sunod. 83 00:04:41,100 --> 00:04:45,370 At kaya pagkatapos ay magpatuloy sa iyo para sa bawat sangkap sa pagkilala sa mga pinakamaliliit na 84 00:04:45,370 --> 00:04:47,690 halaga at pagpapalit ito. 85 00:04:47,690 --> 00:04:53,460 >> Para sa katumbas ko 0, ang pinakaunang elemento sa n minus 1, ikaw ay pagpunta sa ihambing 86 00:04:53,460 --> 00:04:57,820 bawat susunod na halaga matapos na at malaman sa index ng minimum na halaga. 87 00:04:57,820 --> 00:05:02,520 Sa sandaling makita mo ang index ng minimum na halaga, Maaari mong magpalit na halaga ng array 88 00:05:02,520 --> 00:05:05,930 minimum at array I. 89 00:05:05,930 --> 00:05:09,760 >> Ang isa pang uri ng pag-uuri na maaari mong ipatupad ang bubble sort. 90 00:05:09,760 --> 00:05:14,380 Kaya bubble uri iterates sa ibabaw ng listahan paghahambing ng magkakaharap na mga elemento at mga 91 00:05:14,380 --> 00:05:17,720 pagpapalit ang mga elemento na ay nasa maling pagkakasunud-sunod. 92 00:05:17,720 --> 00:05:22,380 At sa ganitong paraan, ang pinakamalaking elemento nasain bubble sa dulo. 93 00:05:22,380 --> 00:05:28,070 At ang listahan ay pinagsunod-sunod sa sandaling walang higit pa mga elemento ay nai-swapped. 94 00:05:28,070 --> 00:05:31,920 >> Kaya mga dalawang mga halimbawa ng mga uri algorithm na maaari mong ipatupad para sa 95 00:05:31,920 --> 00:05:33,230 ang programa find. 96 00:05:33,230 --> 00:05:37,350 Sa sandaling natapos mo ang pag-uuri, at ikaw ay tapos na paghahanap, tapos ka. 97 00:05:37,350 --> 00:05:39,720 Ang pangalan ko ay Zamyla, at ito ay CS50. 98 00:05:39,720 --> 00:05:46,987 >> [MUSIC nagpe-play]