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 zbatohet aktualisht si një kërkim linear. Por ju mund të bëni shumë më mirë se kaq. Kërko lineare zbatohet në O të n kohë, e cila është mjaft i ngadalshëm, edhe pse mund të kërkoni çdo listë që i është dhënë. 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ë 3. 

Mënyra se kërkimi binar punon është se krahasojmë vlerën e mesme të array me gjilpërë, shumë si se si ne u hap një libër telefoni në mes faqe në Javën 0. 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 3, 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, e drejta juaj i detyruar mund të forcojë caqeve kërko vetëm një grimcë më shumë, dhe kështu me radhë e kështu me radhë, deri sa ju gjeni gjilpërë tuaj. 

Pra, çfarë e bën pseudo Kodi duken si? E pra, ndërsa ne jemi ende duke kërkuar nëpërmjet lista dhe ende kanë elemente për të parë në, kemi marrë në qendër i listës dhe krahasoni se Vlera e mesme në gjilpërë tonë. Në qoftë se ata janë të barabartë, atëherë kjo do të thotë ne kemi gjetur gjilpërë, dhe ne mund të 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 ende, atëherë ju kthimit të rreme. Sepse gjilpërë patjetër nuk është në kashtë. 

Tani, një gjë zoti për këtë pseudo Kodi në kërkim binar është se ajo mund të të 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ë kurs. Por e di se ajo është një opsion në qoftë se ju dëshironi të provoni.