Bago gawin ang mga problema, panoorin ang mga lektura 7-8 , basahin at alamin ang " Karagdagang materyales ng ikatlong linggo ". Ang mga ito ay nakatuon sa mga algorithm ng paghahanap (linear at binary), pag-uuri (marami sa kanila!), pati na rin ang gawain ng isang debugger (ang kakayahang magtrabaho kasama ang isang debugger upang i-debug ang mga programa ay isang napakahalagang kasanayan!). Kung ang lahat ay nangyari ayon sa nararapat sa mga lektura at teorya, madali mong masasagot ang mga tanong sa pagsusulit:
Bakit nangangailangan ng binary search ang isang pinagsunod-sunod na hanay?
Bakit ang bubble sort ay tinatantya na O(n2)?
Bakit ang pagtatantya ng insertion sort ay Ω(n)?
Paano gumagana ang pag-uuri ng pagpili? Ilarawan sa tatlong pangungusap (o mas kaunti).
Ano ang pinakamataas na limitasyon (pinakamasamang kaso) kung gaano katagal maaaring tumakbo ang pag-uuri ng pagsasanib?
Binibigyang-daan ka ng debugger ng GDB na i-debug ang isang program. At kung bumalangkas ka nang mas partikular, ano ba talaga ang pinapayagan nitong gawin mo?
Mga layunin
Matutong gumawa ng mga proyektong naglalaman ng maraming file
Matutong magbasa ng source code ng ibang tao
Unawain ang iba't ibang mga algorithm at recursive function
Karamihan sa mga layuning ito ay halos imposible na pormal na suriin. Samakatuwid, mula sa punto ng view ng pormal na pag-verify ng mga problema, may kaunti na mukhang mahirap sa iyo. Gayunpaman, ipinaaalala namin sa iyo: maaari ka lamang matuto ng programming sa pamamagitan ng patuloy na pagsasanay! Samakatuwid, hinihikayat ka namin hindi lamang na lutasin ang mga gawain, ngunit gumastos din ng karagdagang oras at pagsisikap at ipatupad ang lahat ng mga algorithm na tinalakay ngayong linggo. Pasulong!
Magsimula
Alalahanin na para sa mga problema sa pagsasanay sa isa at dalawang linggo, nagsulat ka ng mga programa mula sa simula at lumikha ng iyong sariling pset1 at pset2 na mga direktoryo gamit ang mkdir command . Para sa pagtatalaga ng pagsasanay sa ikatlong linggo, kailangan mong i-download ang pamamahagi (o "distro" kung tawagin namin ito) na isinulat namin at idagdag ang sarili mong mga linya ng code dito. Una, basahin ang aming code at subukang maunawaan ito. Ang pinakamahalagang kasanayan sa linggong ito ay ang pag-aaral kung paano magbasa ng code ng ibang tao. Kaya, mag-log in sa cs50.io at patakbuhin ang command update50 sa isang terminal window upang matiyak na ang bersyon ng workspace ay napapanahon. Kung hindi mo sinasadyang isinara ang terminal window at hindi mo ito mahanap, pumunta sa View menu at tiyaking may check ang Console na opsyon (suriin ito kung hindi). Mag-click sa (+), sa loob ng berdeng bilog sa frame ng terminal window, piliin ang Bagong Terminal . Pagkatapos nito, patakbuhin ang command cd ~/workspace at tiyaking nasa loob ka ng direktoryo ng workspace (ito ang iyong direktoryo). Pagkatapos nito, patakbuhin ang command: wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip upang i-download ang ZIP archive ng problem book sa iyong workspace (ang wget ay ang Linux download command). Kung ok ang lahat, makikita mo ang sumusunod na parirala sa linya: 'pset3.zip' saved Tiyaking na-download mo talaga ang pset3.zip sa pamamagitan ng pagpapatakbo ng command: ls at pagkatapos ay tumakbo unzip pset3.zip upang i-unzip ang file. Kung muli mong patakbuhin ang utos na ls , makikita mo rin ang direktoryo ng pset3 . Pumunta dito sa pamamagitan ng pagpapatakbo ng command cd pset3 at pagkatapos ay humiling na tingnan muli ang mga nilalaman ng direktoryo: ls makikita mo na mayroong dalawang subdirectory sa direktoryong ito: fifteen find Nakakaintriga na!
Maghanap
Sumisid tayo ngayon sa isa sa mga subdirectory na ito. Upang gawin ito, patakbuhin namin ang command: cd ~/workspace/pset3/find Kung ipapakita mo ang mga nilalaman ng folder na ito sa screen (malamang naaalala mo na kung paano gawin ito), ito ang dapat mong makita: helpers.c helpers.h Makefile find.c generate.c Wow, maraming mga file. Ngunit huwag mag-alala, haharapin natin sila ngayon. Ang file generate.c ay naglalaman ng code para sa isang program na gumagamit ng "pseudo-random number generator" (binuo ng drand48 function ) upang makabuo ng malaking bilang ng mga random (talagang pseudo-random, hindi kayang hawakan ng mga computer ang purong randomness!) na mga numero. , at ilagay ang mga ito nang paisa-isa sa linya.I-compile ang program: make generate Ngayon patakbuhin ito sa pamamagitan ng pagpapatakbo ng command: ./generate Ibibigay sa iyo ng program ang sumusunod na mensahe: Usage: generate n [s] Nangangahulugan ito na ang program ay umaasa ng isa o dalawang argumento ng command line. Gamit ang una, n, ay sapilitan; ang numerong ito ay nangangahulugan kung gaano karaming pseudorandom na numero ang gusto mong gawin. Ang parameter s ay opsyonal, gaya ng ipinahiwatig ng mga square bracket. Ang numerong s ay maaaring tawaging "seed" para sa pseudorandom number generator. Sa pamamagitan ng "seed" ang ibig naming sabihin ay ang input data sa pseudorandom number generator na nakakaapekto sa output nito. Halimbawa, kung gumagamit ka ng drand48, una Sa pamamagitan ng pagtawag sa srand48 (isa pang function na ang layunin ay "seed" drand48) na may argumento ng, sabihin nating, 1, at pagkatapos ay tatawagan ang drand48 ng tatlong beses, maaaring bumalik ang drand48 ng 2728, pagkatapos ay 29785, pagkatapos ay 54710. Kung ikaw sa halip na ang nauna, gamit ang drand48, unang tumawag sa srand48 na may argumento ng, sabihin nating, 2, at pagkatapos ay gumamit muli ng drand48 ng tatlong beses, drand48 ay maaaring ibalik ang 59797, pagkatapos ay 10425, pagkatapos ay 37569. Ngunit kung muling makikita mo ang drand48 sa pamamagitan ng pagtawag muli sa srand48 na may argumento na 1, ang resulta ng susunod na tatlong tawag sa drand48 ay makakakuha ka muli ng 2728, pagkatapos ay 29785, pagkatapos ay 54710! Kita mo, lahat ng bagay ay nangyayari para sa isang dahilan. Patakbuhin muli ang programa, sa pagkakataong ito, sabihin n=10, tulad ng ipinapakita sa ibaba; makikita mo ang isang listahan ng 10 pseudo-random na mga numero. ./generate 10 Patakbuhin natin ang programa sa pangatlong beses na may parehong halaga ng n; dapat kang makakita ng isa pang listahan ng 10 numero. Ngayon subukang patakbuhin ang programa na may dalawang mga parameter. Kunin natin ang s=0 tulad ng ipinapakita sa ibaba. ./generate 10 0 Ngayon patakbuhin muli ang parehong utos: ./generate 10 0 Hindi ka man lang makapagtalo: nakita mo muli ang parehong "random" na sequence ng sampung digit. Ito ang mangyayari kung hindi mo papalitan ang pseudorandom number generator seeds. Ngayon tingnan natin ang generate.c program mismo(tandaan kung paano?). Ang mga komento sa simula ng file na ito ay nagpapaliwanag sa pangkalahatang pag-andar ng programa. Ngunit tila nakalimutan nating magkomento sa mismong code. Basahing mabuti ang code at basahin ito hanggang sa maunawaan mo ang kahulugan ng bawat linya. Pagkatapos ay i-comment ang code na ito para sa amin, palitan ang bawat TODO ng isang pariralang naglalarawan sa layunin o functionality ng kaukulang linya o linya ng code. (tandaan: ang unsigned int ay isang “unsigned” int, ibig sabihin ay hindi ito maaaring negatibo). Upang makakuha ng higit pang impormasyon tungkol sa rand o srand, patakbuhin ang: man drand48 o man srand48 Pagkatapos mong magkomento hangga't maaari sa generate.c, muling i-compile ang program upang matiyak na wala kang nasira: make generate Kung hindi na nag-compile ang generate, ayusin kung ano ang iyong nasira :)! Bilang paalala, ang make command ay nag-o-automate ng code compilation, kaya hindi mo na kailangang patakbuhin ang clang command sa pamamagitan ng manu-manong pagpasok ng isang grupo ng mga switch. Ngunit sa katunayan, pinapasimple ng make ang aming input, ngunit sa katunayan, ang parehong clang sa mga parameter na kailangan namin ay nakatago sa likod nito. Gayunpaman, habang lumalaki ang iyong mga programa, hindi na malalaman ni make mula sa konteksto kung paano i-compile ang code. Sa kasong ito, kailangan mong sabihin sa make kung paano i-compile ang mga program, lalo na kung may kinalaman ang mga ito sa paggamit ng iba't ibang source file (tulad ng .c). Upang malutas ang problemang ito, gagamit kami ng mga configuration file (Makefiles) na nagsasabi kung ano ang dapat gawin. Paano nalaman ng make command kung paano tayo dapat mag-compile ng gene? Sa katunayan, gumamit ang team ng configuration file na naisulat na namin. Ang file na ito ay tinatawag na Makefile at ito ay matatagpuan sa parehong direktoryo bilang generate.c . Ang Makefile ay isang listahan ng mga panuntunang tumutukoy kung paano likhain ang file na nabuo mula sa generate.c. Sa file na makikita mo, sa partikular, ang mga nauugnay na linya: generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c Ang unang linya ay nagsasabi na ang isang "target" na tinatawag na generate ay dapat malikha sa pamamagitan ng pagtawag sa command mula sa pangalawang linya. Higit pa rito, ang unang linya ay nagsasabi na ang make na nabubuo ay nakadepende sa generate.c, na nangangahulugan na ang make ay muling bubuo sa mga susunod na pagtakbo kung ang file na iyon ay binago. Hindi isang masamang trick sa pagtitipid ng oras, tama ba? Sa katunayan, patakbuhin muli ang command sa ibaba kung hindi mo binago ang generate.c . make generate Ipapaalam sa iyo na ang generate ay na-update na sa kasalukuyang bersyon. Tandaan : Ang indentation sa simula ng pangalawang linya ay hindi isang pagkakasunod-sunod ng mga puwang, ngunit sa halip ay isang tab na character. Sa kasamaang palad, ang make ay nangangailangan ng mga utos na unahan ng mga tab, kaya mag-ingat na huwag baguhin ang mga ito sa mga puwang o makakaranas ka ng mga kakaibang error! Ang -Werror flag ay nagsasabi sa clang commandituring ang mga babala (masama) bilang mga pagkakamali (mas masahol pa), kaya mapipilitan ka (sa isang mahusay, pang-edukasyon na paraan!) na itama ang mga ito. Ngayon tingnan natin ang find.c file . Tandaan na ang program na ito ay umaasa ng isang command line argument: "igloo", na dapat matagpuan sa isang "haystack" ng mga value. Pagkatapos nito, suriin ang code at i-compile ang programa sa pamamagitan ng pagpapatakbo ng command sa ibaba. make find make basically nagbigay sa amin ng sumusunod: clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Bigyang-pansin! Nag-compile ka lang ng application na binubuo ng isa, ngunit dalawang file: helpers.c at find.c . Paano nalaman ang tungkol dito? Upang maunawaan ito, buksan muli ang Makefile upang makita kung ano talaga ang nangyayari doon. Nasa ibaba ang mga nauugnay na linya. find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Ang ibig naming sabihin sa dependency (pagkatapos ng colon) ay ang anumang pagbabago sa find.c , helpers.c , o helpers.h ay pipiliting gawin na muling buuin ang paghahanap sa susunod na tawagin ito para sa mga layuning iyon. Ngayon patakbuhin ang program na ito sa pamamagitan ng paggawa, halimbawa, ang mga sumusunod: ./find 13 Pagkatapos nito, hihilingin sa iyong magbigay ng isang tiyak na stack (iyon ay, integers), at pakainin sila ng isang straw sa isang pagkakataon. Kapag napagod ka na sa pag-type ng mga numero, pindutin ang key combination Ctrl-D . Ang kumbinasyong ito ay magpapadala sa programa ng isang end-of-file (EOF) na character. Pipilitin ng simbolo ang GetInt function mula sa library ng CS50 na ibalik ang pare-parehong INT_MAX , at ito naman, sa find.c ay pipilitin ang find na ihinto ang pag-type ng "stack". Hahanapin na ngayon ng programa ang karayom sa haystack na iyong ibinigay, at sa kalaunan ay sasabihin nito sa iyo kung ito ay natagpuan. Sa madaling salita, ang programa ay naghahanap ng ilang halaga sa isang array. At least she should, but the catch is na wala pa siyang mahahanap! Ngunit narito ka upang iligtas! Pag-uusapan natin ang kahalagahan ng iyong tungkulin sa ibang pagkakataon. Sa katunayan, ang proseso ng pagbibigay ng haystack ay maaaring awtomatiko, kahit man lang sa pamamagitan ng "pagsasama" ng output ng generate sa find bilang input. Halimbawa, ang command sa ibaba ay nagpapasa ng 1000 pseudorandom na numero na hahanapin, na pagkatapos ay naghahanap sa mga value na iyon para sa 42. ./generate 1000 | ./find 42 Tandaan na kapag ang generate ay pumasa sa raw data na hahanapin, hindi mo makikita ang generate na numero, ngunit makikita mo ang paghahanap na tumatakbo . Bilang kahalili, maaari mong "i-redirect" ang output ng generate sa isang file na may command na tulad nito: ./generate 1000 > numbers.txt Ang mga nilalaman ng file na ito ay maaaring i-redirect sa input ng find gamit ang command: ./find 42 < numbers.txt Tingnan natin muli ang code sa Makefile at pansinin ang sumusunod na linya: all: find generate Nangangahulugan ito na maaari kang bumuo at maghanap sa pamamagitan ng pagpapatakbo ng sumusunod na utos: make all Bukod dito, ang utos sa ibaba ng linyang ito ay katumbas ng utos sa itaas nito, dahil ang make ay bumubuo ng unang entry sa Makefile bilang default. make Kung maaari mo lamang pakuluan ang lahat ng mga gawaing pagsasanay na ito sa isang utos! Ngunit - sayang! Sa wakas, bigyang-pansin ang mga huling linyang ito sa Makefile: clean: rm -f *.o a.out core find generate Ang entry na ito ay nagbibigay-daan sa iyong alisin ang lahat ng mga file na nagtatapos sa .o o tinatawag na core (ipapaliwanag namin ito sa ilang sandali!), at patakbuhin din ang paghahanap o pagbuo ng mga programa nang simple. sa pamamagitan ng pagpapatupad ng linya: Kung gusto mong mag make clean -eksperimento , narito ang isang bagay na dapat mag-ingat: huwag magdagdag, sabihin, *.c sa huling linyang iyon ng Makefile! (bakit?) Lahat ng linyang nagsisimula sa # sign ay mga komento lamang.
Gawain 1: Hanapin
Oras na para sa isang bagay na kawili-wili! Tandaan na ang find.c ay tumatawag sa paghahanap , isang function na ipinahayag sa helpers.h . Sa kasamaang palad, nakalimutan naming ganap na ipatupad ang function na ito sa helpers.c ! (Dapat tandaan na maaari naming ilagay ang mga nilalaman ng helpers.h at helpers.c sa isang find.c . Ngunit kung minsan ay mas mahusay na paghiwalayin ang mga programa sa ilang mga file. Lalo na kung ang ilang mga function, o sa halip na mga function ng utility, ay maaaring maging kapaki-pakinabang para sa iba pang mga programa. Tulad ng mga function ng library ng CS50 halimbawa. Tingnan ang helpers.c at makikita mo na ang paghahanap ay palaging nagbabalik ng false, hindi alintana kung ang ibinigay na halaga ay nasa mga halaga. Isulat muli ang paghahanap upang ito ay gumamit ng linear na paghahanap, nagbabalik ng true , kung ang value ay nasa values at false kung ang value ay wala sa values. Mag-ingat na agad na ibalik ang false kung hindi positive ang n. Kapag handa ka nang suriin ang validity, subukang tawagan ang sumusunod na command: Dahil naka-print ang isa sa mga ./generate 1000 50 | ./find 127 numero na may generate kapag ang 50 ay seeded ay 127, ang iyong code ay dapat mahanap ang karayom! Para sa kaibahan, subukan ang command na ito: ./generate 1000 50 | ./find 128 Dahil ang 128 ay wala sa hanay ng mga numero na nabuo sa pamamagitan ng generate noong 50 ay seeded, ang iyong code ay hindi dapat mahanap ang "karayom" . Patakbuhin ang iba pang mga pagsubok sa pamamagitan ng pagpapatakbo ng gene na may ilang buto, pagsusuri sa output, at paghahanap ng karayom na dapat ay nasa haystack. Tandaan na ang pangunahing sa find.c ay isinulat sa paraang ang find ay nagbabalik ng 0 kung ang "karayom" ay natagpuan, kung hindi, ito ay nagbabalik ng 1. Maaari mong suriin ang tinatawag na "output code" na pangunahing nagbabalik kapag naisakatuparan pagkatapos ng pagtakbo ng iba mga utos echo $? . Halimbawa, kung tama ang iyong pagpapatupad ng paghahanap, kung tatakbo ka, ./generate 1000 50 | ./find 127 echo $? makikita mo ang 0, habang ang 127 ay kabilang sa 1000 na mga numero na output sa pamamagitan ng pagbuo na may seed na 50, kaya ang paghahanap na iyong isinulat ay dapat na bumalik na totoo. Sa kasong ito, ang pangunahing (isinulat namin) ay dapat magbalik ng 0 (iyon ay, exit). Kung ibibigay mo ang sumusunod na input ./generate 1000 50 | ./find 128 echo $? , makikita mo ang 1 dahil ang 128 ay hindi kabilang sa 1000 na numero na na-output sa pamamagitan ng pagbuo na may seed na 50. Sa kasong ito, ang paghahanap (isinulat mo) ay magbabalik ng false, at pangunahing (isinulat namin ) ay magbabalik ng 1 ( at pagkatapos ay tapusin ang trabaho). Naiintindihan mo ba ang lohika? Kapag handa na ang lahat para suriin gamit ang check50, patakbuhin ang sumusunod na command: check50 2015.fall.pset3.find helpers.c Siyanga pala, hindi ka dapat masanay sa pagsubok ng iyong code gamit ang check50 bago mo ito subukan. Pagkatapos ng lahat, ang check50 ay hindi talaga umiiral, kaya ang pagpapatakbo ng code gamit ang iyong sariling mga sample ng input, paghahambing ng aktwal na output sa inaasahang output, ay ang pinakamahusay na ugali na maaari mong makuha sa puntong ito. Ito ay totoo, huwag maging adik! Kung interesado kang makipaglaro sa pagpapatupad ng paghahanap ng mga assistant ng cs50, patakbuhin ang command na ito: ~cs50/pset3/find
Pag-uuri
Ang linear na paghahanap ay hindi isang bagay na talagang kahanga-hanga, ngunit mula sa mga unang lektura (at sa ikapitong inulit namin muli ang trick na ito!) naaalala mo na mas mabilis kang makakahanap ng karayom sa isang haystack. Ngunit kailangan muna nating ayusin ang ating haystack. Tandaan na ang find.c ay tumatawag ng sort , isang function na ipinahayag sa helpers.h . Sa kasamaang palad, "nakalimutan" naming ganap na ipatupad ang feature na ito sa helpers.c ! Tumingin sa helpers.c at makikita mo ang pag-uuri na iyon ay bumalik kaagad, kahit na ang pangunahing function ng find ay talagang ipinapasa ito sa aktwal na array. Ngayon tandaan ang array declaration syntax. Hindi mo lang tinukoy ang uri ng elemento ng array na ito, ngunit tinukoy mo rin ang laki nito sa mga square bracket. Ito ang ginagawa namin para sa haystack sa find.c : int haystack [MAX]; Ngunit kapag binabaybay ang isang array, tinukoy mo lang ang pangalan nito. At ginagawa namin ito nang eksakto sa parehong paraan kapag dumaan kami sa haystack para mag-sort sa find.c : sort (haystack, size); (Hulaan kung bakit namin ipinapasa ang laki ng array na iyon nang hiwalay?) Kapag nagdeklara kami ng function na kumukuha ng one-dimensional array bilang argumento, hindi namin kailangang tukuyin ang laki ng array . Gayundin, hindi namin ginawa ito noong nagdeklara kami ng pag-uuri sa helpers.h (at helpers.c): void sort (int values [] int n); Ipatupad ang pag-uuri upang ang function ay aktwal na pag-uri-uriin ang hanay ng mga numero mula sa maliit hanggang sa malaki. Kailangan nitong magpatakbo ng oras na katumbas ng O(n 2 ), kung saan ang n ay ang laki ng array. Malamang na gusto mong ipatupad ang bubble sort, selection sort, o insertion sort, gaya ng nalaman namin tungkol sa mga nasa ikatlong linggo. Gayunpaman, mahalagang tandaan: walang "tama" na paraan upang ipatupad ang mga algorithm na ito. Mayroong isang malaking bilang ng mga pagkakaiba-iba. Sa katunayan, maaari mong palaging mapabuti ang mga ito kung nakikita mong angkop, hangga't ang iyong pagpapatupad ay nagko-converge sa O(n2 ) . Gayunpaman, iwanan ang eksperimento sa function body, at upang pasimplehin ang pagsubok, huwag baguhin ang aming deklarasyon ng pag-uuri. Dapat itong magmukhang ganito: void sort (int values [] int n); Dahil nagbabalik ang function ng void value, hindi ito dapat magbalik ng pinagsunod-sunod na array. Sa halip, dapat itong "mapanirang" pag-uri-uriin ang aktwal na hanay na "tinatakbo" nito, na gumagalaw sa mga elemento nito. Sa ikaapat na linggo, tatalakayin natin na ang mga array ay ipinapasa sa pamamagitan ng sanggunian sa halip na sa pamamagitan ng halaga. Ibig sabihin, hindi makakatanggap ang sort ng mga kopya ng array, ngunit ang orihinal na array mismo. Bagama't hindi mo mababago ang aming deklarasyon ng pag-uuri, maaari mong palaging tukuyin ang iyong sariling function sa helpers.c, na maaaring tawagin mula sa sort. Magpasya para sa iyong sarili kung paano pinakamahusay na subukan ang iyong pagpapatupad ng pag-uuri. Huwag kalimutan na tutulungan ka ng printf at GDB! At huwag kalimutan na maaari kang lumikha ng parehong pagkakasunud-sunod ng mga pseudo-random na numero nang paulit-ulit sa pamamagitan ng tahasang pagtukoy sa mga halaga ng binhi para sa pagbuo.
Binary na paghahanap, mga tip
Ang unang bagay na kailangan mong maunawaan tungkol sa function ng paghahanap ay mayroon na kaming nakasulat na code (distribusyon). Pinupunan lang namin ang ilang mga puwang sa umiiral na code. Ang find.c program ay humihiling ng input ng mga numero (iyon ay, upang punan ang isang "stack"), at pagkatapos ay naghahanap ng isang "karayom" dito sa kahilingan ng user, gamit ang pag-uuri at paghahanap - mga function na tinukoy sa helpers.c . Kaya, ang paghahanap ay nakasulat na, kailangan nating magsulat ng mga katulong . Kaya narito ang kailangan nating gawin:
Ipatupad ang paghahanap. Ang function na ito ay dapat magbalik ng true kung ang halaga ay makikita sa stack at false kung wala ito.
Ipatupad ang sort, isang function na nag-uuri ng isang array ng mga value.
Sa una, ang paghahanap ay ipinatupad bilang linear. Ngunit maaari kang gumawa ng mas mahusay. Ang linear search algorithm ay tumatakbo sa O(n) na oras . Ang iyong gawain ay magsulat ng isang binary search algorithm. Ang oras ng pagpapatupad nito ay O(log n) . Gayunpaman, ang problema nito ay nangangailangan ito ng pinagsunod-sunod na data bilang input, kung hindi man ay hindi ito gagana. Naaalala mo ang halimbawa ng punit na libro, at malamang na alam mo kung bakit ganito. Kung dumaan ka sa isang binary na paghahanap sa pamamagitan ng mga elemento at wala nang natitira sa mga ito (iyon ay, wala nang "karayom" sa "stack" na ito), kailangan mo ang function upang ibalik ang false. Maaaring ipatupad ang binary search nang paulit-ulit o recursively (nag-usap si David Malan tungkol sa recursion sa ikawalong lecture).
Pagkatapos nito, patakbuhin ang command 
GO TO FULL VERSION