[Muzika] 

DOUG Lloyd: Në rregull. Pra, kërko binar është një Algorithm ne mund të përdorim për të gjetur një element brenda një grup. Ndryshe kërkim lineare, ajo kërkon një kusht të veçantë të plotësohen paraprakisht, por ajo është aq shumë më efikas nëse se gjendja është, në fakt, u takuan. 

Pra, çfarë është ideja këtu? është përça dhe sundo. Ne duam të zvogëluar madhësinë e zona e kërkimit nga gjysmë çdo herë në mënyrë që të gjeni një numër të synuar. Kjo është ajo ku se gjendja vjen në lojë, edhe pse. Ne vetëm mund të levave fuqinë e eliminimin gjysma e elementeve edhe pa e kërkuar në ata nëse array është e renditura. 

Në qoftë se kjo është një përzierje e plotë lart, ne nuk mund vetëm nga dora hidhni gjysmën e elementeve, sepse ne nuk e dimë se çfarë ne jemi hidhni. Por në qoftë se array është e renditura, ne mund ta bëjmë këtë, sepse ne e di se çdo gjë në la e ku ne aktualisht jemi të duhet të jetë më e ulët se Vlera ne jemi aktualisht në. Dhe çdo gjë të e drejta e ku jemi duhet të jetë më i madh se vlera ne jemi aktualisht në kërkim në. 

Pra, çfarë është pseudokod hapat për kërkimin binar? Ne përsëris këtë proces deri në grup ose, si ne të vazhdojë përmes, nën vargjeve, copa të vogla të array origjinal, është i madhësisë 0. Llogarit midpoint e array aktuale sub. 

Nëse vlera jeni duke kërkuar për të është në këtë element të vektorit, të ndaluar. Keni gjetur atë. Kjo është e madhe. Përndryshe, në qoftë se objektivi është më pak se çfarë është në mes, kështu që nëse vlera ne jemi duke kërkuar për të është më e ulët se ajo që ne shohim, përsëris këtë proces përsëri, por ndryshojë pikën fund, në vend për të qenë origjinale përfunduar koleksion të plotë, të jetë vetëm në të majtë e ku ne vetëm shikuar. 

Ne e dinim se mesme ishte shumë i lartë, ose objektivi ishte më pak se mes, dhe kështu ajo duhet të ekzistojë, nëse ajo ekziston fare në grup, diku në të majtë të midpoint. Dhe kështu që ne do të vendosur array vend vetëm në të majtë i midpoint si pikë e re në fund. Në anën tjetër, në qoftë se objektivi është më të madhe se ajo që është në mes, ne bëjmë të njëjtën gjë e saktë proces, por në vend të kësaj ne ndryshojë pikënisjen të jetë vetëm në të djathtë të midpoint ne vetëm llogaritur. Dhe pastaj, ne fillojmë procesin përsëri. 

Le të kujtoj këtë, në rregull? Pra, ka një shumë ndodh dhe në këtu, por këtu është një grup prej 15 elementeve. Dhe ne jemi duke shkuar për të mbajtur gjurmët e një shumë më të gjëra në këtë kohë. Pra, në kërkim linear, ne ishim vetëm kujdeset për një objektiv. Por këtë herë ne duam të kujdes për ku jemi ne filluar të duken, ku jemi ndalur duke kërkuar, dhe çfarë është midpoint e array aktuale. Pra, këtu ne do të shkojmë me kërkimin binar. Ne jemi shumë e shumë të mirë për të shkuar, e drejtë? Unë jam vetëm duke shkuar për të vënë poshtë poshtë këtu një grup i treguesve. Kjo është në thelb vetëm ajo që elementi e grup ne jemi duke folur rreth. Me kërkimin lineare, ne kujdes, duke qenë se ne duhet të dini se sa Elementet ne jemi iterating mbi, por ne fakt nuk e kujdesit çfarë element ne jemi aktualisht në kërkim në. Në kërkim binar, ne bëjmë. Dhe kështu ata janë vetëm atje si një udhëzues të vogël. 

Pra, ne mund të fillojnë, apo jo? E pra, jo fare. Mos harroni atë që kam thënë për kërkimin binar? Ne nuk mund ta bëjë këtë në një array Unsorted ose tjetër, ne nuk jemi të garantuar se elemente ose vlerat e caktuara nuk janë të të qenit aksidentalisht fshi kur ne vetëm vendosni të injorojë gjysmën e vektorit. 

Pra, hap një me kërkimin binar është që ju duhet të keni një rrjet të renditura. Dhe ju mund të përdorni ndonjë nga klasifikim Algoritme ne kemi biseduar për për të merrni ju në atë pozitë. Deri tani, ne jemi në një pozicion ku ne mund të kryejë kërkimin binar. 

Pra, le të përsëris procesin hap pas hapi dhe për të mbajtur gjurmët e asaj që po ndodh si të shkojmë. Pra, së pari ne duhet të bëjmë është të llogaritur midpoint e array aktuale. E pra, ne do të themi ne jemi, së pari të gjithë, duke kërkuar për vlerën 19. Ne jemi duke u përpjekur për të gjetur numrin 19. Elementi i parë i kësaj grup është vendosur në indeksin zero, dhe elementi i fundit i kësaj grup është vendosur në indeksin e 14. Dhe kështu që ne do të thërrasë ato fillimin dhe fundin. 

Pra, ne llogarisim midpoint nga duke shtuar plus 14 0 ndarë nga 2; midpoint shumë i thjeshtë. Dhe ne mund të themi se midpoint tani është 7. Pra është 15 ajo që ne jemi duke kërkuar për? Jo nuk eshte. Ne jemi në kërkim 19. Por ne e dimë se 19 është më i madh se ajo që kemi gjetur në mes. 

Pra, çfarë mund të bëjmë është ndryshojë pikënisjen të jetë vetëm në të djathtë e midpoint, dhe përsërisin procesin përsëri. Dhe kur e bëjmë këtë, ne tani thonë se pikë e re e fillimit është koleksion vend 8. Ajo që ne kemi bërë në mënyrë efektive është gjithçka injoruar në të majtë të 15. Ne e kemi eliminuar gjysmën e problemit, dhe tani, në vend që të kërkoni mbi 15 elemente në grup tonë, ne vetëm duhet të kërkoni mbi 7. Pra 8 është pikë e re e fillimit. 14 është ende pikë në fund. 

Dhe tani, ne do të shkojmë mbi këtë përsëri. Ne llogarisim midpoint e ri. 8 plus 14 është 22, të ndarë nga 2 është 11. A është kjo ajo që ne jemi duke kërkuar për? Jo nuk eshte. Ne jemi duke kërkuar për një vlerë që është më pak se ajo që ne vetëm e gjeti. Pra, ne jemi duke shkuar për të përsëritur procesi përsëri. Ne jemi duke shkuar për të ndryshuar pikën në fund të të jetë vetëm në të majtë të midpoint. Pra, pikë e re në fund të bëhet 10. Dhe tani, kjo është vetëm një pjesë e array ne kemi për të zgjidhur nëpërmjet. Pra, ne kemi eliminuar tani 12 e 15 elementeve. Ne e dimë se nëse 19 ekziston në grup, atë duhet të ekzistojë diku në mes të elementit numër 8 dhe element numër 10. 

Pra, ne llogarisim midpoint e re përsëri. 8 plus 10 është 18, të ndarë nga 2 është 9. Dhe në këtë rast, ja, Objektivi është në mes. Ne kemi gjetur pikërisht ajo që ne jemi duke kërkuar për të. Ne mund të ndalet. Ne përfundoi me sukses një kërkim binar. Në rregull. Pra, ne e dimë këtë algoritmi punon në qoftë se objektivi është diku brenda array. E bën këtë punë algorithm nëse objektiv nuk është grup? E pra, le të fillojë atë përsëri, dhe këtë herë, le të shohim për elementin 16, e cila vizualisht ne mund të shohim nuk ekziston askund në rrjet. 

Pika e fillimit është përsëri 0. Pika Fundi është përsëri 14. Ata janë indekset e parë dhe Elementet e fundit të vektorit të plotë. Dhe ne do të kalojnë nëpër procesin e ne vetëm shkoi nëpër përsëri, duke u përpjekur për të gjetur 16, edhe pse me sy, ne tashmë mund të them se kjo nuk do të jetë atje. Ne vetëm duam të sigurohemi këtë algorithm do të, në fakt, ende punojnë në një farë mënyre dhe jo vetëm të na lënë mbërthyer në një lak të pafund. 

Pra, çfarë është hapi i parë? Llogarit midpoint e array aktuale. Çfarë është midpoint e array aktuale? E pra, kjo është 7, e drejtë? 14 plus 0 ndarë nga 2 është 7. Është 15 atë që ne jemi duke kërkuar për? Jo. Është mjaft i afërt, por ne jemi duke kërkuar për një vlerë pak më të madhe se kaq. 

Pra, ne e dimë se ajo do të të jetë askund në të majtë të 15. Objektiv është më e madhe se çfarë është në midpoint. Dhe kështu që ne kemi vendosur pikë të re të fillojë të të jetë vetëm për të drejtën e mes. Midpoint është aktualisht 7, kështu që le të themi pika e re e fillimit është 8. Dhe ajo që ne kemi në mënyrë efektive bërë përsëri është injoruar të gjithë gjysmën e majtë të vektorit. 

Tani, ne përsëris procesin e një më shumë kohë. Llogaritni midpoint e ri. 8 plus 14 është 22, të ndarë nga 2 është 11. Është 23 atë që ne jemi duke kërkuar për? Për fat të keq, nuk ka. Ne jemi duke kërkuar për një vlerë të që është më pak se 23. Dhe kështu në këtë rast, ne jemi duke shkuar për të ndryshuar pikën fund të jetë vetëm në të majtë të midpoint e tanishëm. Midpoint aktual është 11, dhe kështu që ne do të vendosur në pikën e re në fund për herën tjetër ne do të shkojmë përmes këtij procesi deri në 10. 

Përsëri, ne do të shkojmë nëpër procesin përsëri. Llogarit midpoint. 8 plus 10 ndarë nga 2 është 9. Është 19 atë që ne jemi duke kërkuar për? Për fat të keq, nuk ka. Ne jemi ende në kërkim të një numër më pak se. Pra, ne do të ndryshojë pikën e fundit këtë herë të jetë vetëm në të majtë të midpoint. Midpoint është aktualisht 9, kështu që pikë në fund do të jetë 8. Dhe tani, ne jemi vetëm në kërkim në një grup të vetëm element. 

Çfarë është midpoint e kësaj grup? E pra, ajo fillon në 8, ajo përfundon në 8, midpoint është 8. A është kjo ajo që ne jemi duke kërkuar për? A jemi duke kërkuar për 17? Jo, ne jemi duke kërkuar për 16. Pra, nëse ajo ekziston në grup, ajo duhet të ekzistojë diku në të majtë të ku ne aktualisht janë. Pra, çfarë do të shkojmë të bëjmë? E pra, ne do të vënë pikën në fund të jetë vetëm në të majtë të midpoint e tanishëm. Pra, ne do të ndryshojë pikën fund në 7. A e shihni se çfarë sapo ka ndodhur këtu, edhe pse? Look up këtu tani. 

Filloni tani është më i madh sesa në fund. Efektive, të dy skajet e array tonë kanë kaluar, dhe pika e fillimit është tani pas pikë në fund. E pra, kjo nuk ka të bëjë ndonjë kuptim, apo jo? Deri tani, ajo që mund të them është që ne kanë një grup nën të madhësisë 0. Dhe një herë ne jemi duke marrë për kjo pikë, ne tani mund të të garantojë se elementi 16 nuk ekziston në grup, sepse pika e fillimit dhe pikë në fund kanë kaluar. Dhe kështu që nuk është aty. Tani, vini re se kjo është pak ndryshme se pika e fillimit dhe në fund më tepër është e njëjtë. Nëse do të kishte qenë në kërkim për 17, ai do të ketë qenë në grup, dhe pika e fillimit dhe pikë në fund të atij përsëritje fundit para se ato pika kaluar, ne do të kemi gjetur 17 atje. Është vetëm kur ata kalojnë që ne mund të garantojë se elementi nuk ka ekzistojnë në rrjet. 

Pra, le të marrin një shumë më pak Hapat sesa kërkim linear. Në rastin më të keq, kemi pasur për të ndarë një listë të elementeve n në mënyrë të përsëritur në gjysmë për të gjetur objektivin, ose për shkak se elementi objektiv do të jetë diku në të fundit ndarje, apo nuk ekziston fare. Pra, në rastin më të keq, ne duhet të ndarë të array-- nuk e dini? Log i herë n; ne keni për të prerë problemin në gjysmën e një numër të caktuar të kohës. Ky numër i herë është log n. 

Çfarë është skenari më i mirë? E pra, koha që ne e parë llogaritur midpoint, ne gjejmë atë që ne jemi duke kërkuar për. Në të gjitha e mëparshme Shembujt në kërkim binar ne kemi shkuar pak më shumë, nëse do të kishim qenë në kërkim për elementin 15, ne do të kemi gjetur se menjëherë. Kjo ishte në fillim. Kjo ishte midpoint e përpjekja e parë në një ndarje e një ndarje në kërkim binar. 

Dhe kështu në më të keq rast, kërko binar shkon në log n, e cila është në thelb e mirë se kërko lineare, në rastin më të keq. Në rastin më të mirë, binar Kërko shkon në omega e 1. Pra, kërko binar është një shumë më mirë se kërkimi lineare, por ju duhet të merren me procesin e sorting grup tuaj të parë para se ju mund të levave fuqinë e kërkimit binar. 

Unë jam Doug Lloyd. Kjo është CS 50.