[MUSIC Playing] 

ZAMYLA CHAN: Gjëja e parë që ju mund Njoftimi në lidhje me gjeni është se ne tashmë kanë Kodi shkruar për ne. Kjo quhet kod shpërndarjes. Pra, ne nuk jemi vetëm shkrim e jona kodin nga e para më. Më saktë, ne jemi duke plotësuar voids në disa kodin para-ekzistuese. 

Programi find.c bën për numrat për të mbushur kashtë, kërkon kashtë për një përdorues dorëzuar gjilpërë, dhe kjo e bën këtë duke e quajtur lloj dhe kërkimi, funksionet e përcaktuar në helpers.c. Pra find.c është shkruar tashmë. Puna juaj është për të shkruar ndihmëtarë. 

Pra, çfarë po bëjmë? Ne jemi duke zbatuar dy funksione. Search, e cila jep true nëse një vlerë e është gjetur në kashtë, duke u kthyer false nëse vlera është jo në kashtë. Dhe atëherë ne jemi edhe zbatimin lloj të cilat llojet array quajtur vlerat. 

Pra, le të trajtuar kërkim. Kërko aktualisht është zbatuar si një kërko lineare, por ju mund të bëni shumë më të më mirë se kaq. Kërko linear është zbatuar në O kohe N, i cili është mjaft ngadalshëm. Edhe pse, ajo mund të kërkoni ndonjë listë jepet. Detyra jote është për të zbatuar kërko binar, i cili ka drejtuar kohë o të log n. Kjo është shumë e shpejtë. 

Por ka një kusht. Kërko Binary mund të kërkoni vetëm përmes listave të para-renditura. Pse është kjo? 

E pra le të shikojmë një shembull. Duke pasur parasysh një sërë vlerash, kashtë, ne do të jetë në kërkim për një gjilpërë. Dhe në këtë shembull, numër i plotë tre. Mënyra se kërkimi binar punon është se krahasojmë vlerën e mesme të array me gjilpërë, shumë si se si ne kemi hapur një Phonebook në mes faqe në javë zero. 

Pra, pasi krahasuar vlerën e mesme të gjilpërë, ju mund të hidhni ose majtas ose gjysmën drejta e array duke forcuar kufijtë e tu. Në këtë rast, që nga tre, gjilpërë tonë, është më pak se 10, vlera mesatare, drejta e lidhur mund të ulet. Por të përpiqet për të bërë kufijtë e tu sa i ngushtë të jetë e mundur. Nëse vlera e mesme nuk është gjilpërë, atëherë ju e dini që ju nuk keni nevojë për të të përfshijë atë në kërkimin tuaj. Pra, ju jeni të drejtë lidhur mund të forcojë caqeve kërko vetëm një grimcë më shumë, dhe kështu me radhë e kështu me radhë deri sa të ju gjeni gjilpërë tuaj. 

Pra, ajo që duket si pseudokod? E pra, ndërsa ne jemi ende në kërkim përmes lista dhe ende kanë elemente të shikoni në, kemi marrë mes të listës, dhe krahasoni se vlera e mesme të gjilpërë tonë. Në qoftë se ata janë të barabartë, atëherë kjo do të thotë ne kemi gjetur gjilpërën dhe ne mund kthim i vërtetë. 

Përndryshe, nëse gjilpëra është më pak se vlera e mesme, atëherë kjo do të thotë që ne mund të hidhni gjysmën e duhur, dhe vetëm kërkoni në anën e majtë të array. Përndryshe, ne do të kërko anën e djathtë të vektorit. Dhe në fund, nëse ju nuk keni ndonjë më shumë elemente lënë për të kërkuar, por ju nuk kanë gjetur gjilpërë tuaj akoma, atëherë ju kthimit të rreme sepse gjilpërë definitivisht nuk është në kashtë. 

Tani një gjë zoti për këtë pseudokod në kërkim binar është se ajo mund të jetë e interpretohet si ose një përsëritës ose zbatimin recursive. Pra, kjo do të ishte gjithkund rekursive në qoftë se ju të quajtur funksionin e kërkimit në kërkim të funksionojë në të dyja gjysmën e vektorit. Ne do të mbulojë recursion pak më vonë në Sigurisht, por e di se ajo është një opsion në qoftë se ju dëshironi të provoni. 

Tani le të shohim në lloj. Renditur merr një rrjet dhe numër i plotë n, e cila është madhësia e array. Tani ka lloje të ndryshme të ndryshme në terezi, dhe ju mund të shikoni në disa pantallona të shkurtra për popull dhe shpjegime. Lloji kthimit për tonë Funksioni lloj është e pavlefshme. Kështu që do të thotë se ne nuk do të kthehen çdo rrjet nga lloji. Ne jemi të vërtetë do të ndryshojë shumë array që u miratua në ne. 

Dhe kjo është e mundur për shkak se vargjeve janë kaluar duke iu referuar në C. Tani ne do të shih më shumë për këtë më vonë, por Dallimi thelbësor në mes të kalimit në diçka si një numër të plotë dhe kalimin në një rrjet, është se kur ju të kalojë në një numër të plotë, C është vetëm do të të bëjë një kopje të këtij numër të plotë dhe të kalojë ajo te funksionit. Ndryshueshme origjinale nuk do të ndryshohet një herë funksioni është përfunduar. Me një grup, nga ana tjetër, është nuk do të bëjë një kopje, dhe ju do të në të vërtetë të redaktimi vetë shumë array. 

Pra, një lloj lloji është lloj përzgjedhje. Zgjedhja lloj punon duke filluar nga ora në fillim, dhe pastaj ju iterate mbi dhe për të gjetur elementin më të vogël. Dhe pastaj ju bie në ujdi që më të vogël element me një të parë. Dhe pastaj ju hyni në elementin e dytë , Të gjejnë tjetër më të vogël element, dhe pastaj shkëmbim se me Elementi i dytë në grup, sepse elementi i parë zgjidhet tashmë. Dhe kështu atëherë ju të vazhdojë për çdo element në identifikimin më të vogël Vlera dhe shkëmbejnë atë. 

Sepse unë barabartë 0, elementin e parë të n minus 1, ju do të jeni për të krahasuar çdo vlerë tjetër pas kësaj dhe për të gjetur indeksi i vlerës minimale. Pasi ju të gjeni indeksin e vlerës minimale, ju mund të bie në ujdi se vlera e array minimale dhe array I. 

Një tjetër lloj i lloj që ju mund të zbatuar është flluskë lloj. Kështu iterates flluskë lloj mbi listën e krahasuar elementet ngjitur dhe shkëmbejnë elementet që janë në mënyrë të gabuar. Dhe në këtë mënyrë, elementi më i madh do flluskë deri në fund. Dhe lista të zgjidhet një herë jo më shumë elemente janë swapped. 

Pra, ata janë dy shembuj të lloj algoritme që ju mund të zbatojë për programi gjeni. Pasi të keni mbaruar lloj, dhe ju keni bërë kërkimin, ju jeni mbaruar. Emri im është Zamyla, dhe kjo është CS50. 

[MUSIC Playing]