[Musika jotzen] 

DOUG LLOYD: Ondo da. Beraz, bilaketa bitarra da algoritmoa erabili ahal izango dugu array baten barruan elementu bat aurkitzeko. Bilaketa lineala ez bezala, hura eskatzen batean baldintza bereziak izango dira, aldez aurretik ezagutu, baina hain da askoz eraginkorragoa bada Baldintza hori da, hain zuzen ere, ezagutu. 

Beraz, zer da ideia hemen? Banatu eta agindu da. Tamaina murriztu nahi dugu Bilaketa-denbora erdia bakoitzak zona Helburu zenbaki bat aurkitzeko. Hau non baldintza dela sartzen da jokoan, baina. Dugu bakarrik leverage boterea ezabatuz elementuak erdia are begiratu gabe Array bada horiek ordenatuko da. 

Nahasketa up bat da, bada Ezin dugu besterik escutic elementuak erdia baztertzen dituelako ez dakigu zer baztertzen ari gara. Baina array ordenatuko da, bada, Hori egin ahal izango dugu, garelako dena dela jakin non gaur egun gara geldituak baino txikiagoa izan behar du balio gaur egun ari gara. Eta guztia egin non gauden eskubidea balioa baina handiagoa izan behar du Une gara begira. 

Beraz, zein da pseudocode bilaketa bitarra urratsak? Prozesu hau errepikatu dugu arte array edo, bidez jarraitu dugu, sub matrizeak, pieza txikiagoak jatorrizko array, tamaina 0 da. Kalkulatu erdigunea Gaur egungo sub array. 

Balioa bila bazabiltza da array elementu horretan, gelditzeko. Aurkitu duzu. Hori handia. Bestela, helburua bada Zer da erdian baino gutxiago, beraz, ez dugu bilatzen ari balioa bada Ba ikusten duguna baino txikiagoa da, Prozesu hau errepikatu berriro, baina aldatu amaiera puntua, ordez original izatearen multzo osoa bete, besterik ezkerrera izan non begiratu besterik ez dugu. 

Bagenekien erdian izan ez bada ere, edo helburuaren erdian baino txikiagoa izan zen, eta beraz, existitu behar da, bada batere array existitzen, nonbait erdigunea ezkerreko. Eta beraz, array ezarri beharko dugu besterik ezkerreko kokapena erdigunea amaieran puntu berri gisa. Aitzitik, helburu bada Zer da erdian baino handiagoa, zehatza bera egiten dugu prozesua, baina horren ordez dugu Irteeran aldatu ahal besterik erdigunea eskubidea kalkulatzen besterik ez dugu. Eta orduan, prozesua hasten gara berriro. 

Dezagun Ikusteko honetan, OK? Beraz, ez da asko gertatzen da eta hemen da, baina hemen 15 elementuen array bat. Eta ari gara egon jarraipena joan a lot more stuff denbora honen. Beraz, bilaketa lineala ere, izan ginen besterik helburu zaintzearen. Baina une honetan egin nahi dugu arduratu non gauden begiratzen hasita, non ari ari gara gelditzen, eta zer da erdigunea Gaur egungo array. Hortaz, hona hemen bilaketa bitarra joan ginen. Nahiko askoz ona joan, lasai egongo gara? Besterik ez naiz behera jarri nahi dut azpitik hemen indizeak multzo bat. Hau da, funtsean, zer elementu Array hizketan ari garen. Bilaketa lineala, gara zaintzeko, zeren dugun bezala Badakizu zenbat behar elementu ari gainean errepikatzean dugu, baina ez ditu zaintzen dugu zer elementu Une gara begira. Bilaketa bitarra, egiten dugu. Eta beraz, horiek besterik ez dira Han gida txiki bat bezala. 

Beraz, hasi ahal izango dugu, ezta? Beno, ez da nahiko. Gogoratu zer esan dut bilaketa bitarra buruz? Ezin dugu ezer egingo batean Sailkatu array edo, bestela, ez gara hori bermatuz elementu edo balore jakin batzuk ez dira ustekabean izateaz baztertzea denean besterik ez dugu array erdia alde batetara utzi erabakitzeko. 

Beraz, bilaketa bitarra bat zapaldu da ordenatuko array bat izan behar duzu. Eta sailkatzeko edozein erabili ahal izango duzu hitz egin dugu algoritmoak you get to posizio horretara. Beraz, gaur egun, ez gara posizio bat, non ere bilaketa bitarra egin ahal izango dugu. 

Hargatik errepikatu prozesua pausoz pauso eta mantentzeko Zer ari da gertatzen joan gara pista. Beraz, lehenengo kalkulatu da egin behar dugu Gaur egungo array erdigunea. Beno, esan dugu ari gara, lehen guztiak, 19 balio du bila. 19 zenbakira bilatzen saiatzen ari gara. Honen lehenengo elementua array da indizea zero kokatuta dago, eta horren azken elementua array da indizea 14 at dago. Eta beraz, hasieratik horiek eta azkenean deitu dugu. 

Beraz arabera erdigunea kalkulatzeko dugu 0 plus 14 2 banatuta gehituz; nahiko erraza erdigunea. Eta hori esan dezakegu erdigunea da orain 7. Beraz, 15 da zer bilatzen ari gara? Ez, ez da. Ari gara 19 bila. Baina badakigu 19 handiagoa zer aurkitu erdian gu baino. 

Beraz, zer egin ahal izango dugu Irteeran aldatu to besterik eskubidea izango erdigunea, eta errepikatu prozesua berriro. Eta noiz egiten dugu, orain esan dugun Irteeran berria array kokapena 8 da. Zer eraginkorrean dugu egin da bazterrera utzi 15 ezkerreko dena. Erdi Nik kendu dugu Arazoaren, eta orain, ordez bilatu beharrean gure array elementu 15 baino gehiago, 7 gehiagoko bilatu beharko dugu. Beraz, 8 Irteeran berria da. 14 amaieran puntua da oraindik. 

Eta orain, hori baino gehiago ere joaten gara. Erdigunea berria kalkulatu dugu. 8 plus 14 22 da, 2 11 da banatuta. Hau da, zer bilatzen ari gara? Ez, ez da. Ari gara, hori da balio baten bila besterik zer aurkitu genuen baino gutxiago. Beraz, errepikatu egingo da prozesua berriro. Amaieran puntua aldatzen goaz besterik erdigunea ezkerreko izan. Beraz, amaieran puntu berria bihurtzen 10. Eta orain, horren zati bat bakarrik da array bidez ordenatzeko behar dugu. Beraz kendu orain dugu 12 15 elementuetako. Badakigu 19 baldin bada array batean badago, nonbait existitzen behar elementu arteko 8 eta 10 elementu kopurua. 

Beraz, erdigunea berria kalkulatu dugu berriro. 8 plus 10 18 da, 2 9 da banatuta. Eta, kasu honetan, begiratu, helburu erdian dago. Zehazki zer bilatzen ari gara aurkitu dugu. Gelditu ahal izango dugu. Arrakastaz burutu dugu bilaketa bitarra bat. Ados. Beraz, algoritmo hau ezagutzen dugun lan egiten du xede da bada nonbait array barruan. Algoritmoa lan badu helburua ez da array? Beno, goazen hasi da berriro, eta oraingo honetan, ikus ditzagun elementu 16, ikusmen ikusi ahal izango dugu ez da existitzen lekutan array. 

Irteeran da berriro 0. Amaieran puntua da berriro 14. Horiek dira lehen indizeak eta osoa array azken elementuak. Eta besterik ez dugu prozesuan zehar joan beharko dugu ziren handik berriro, 16 aurkitu nahian, nahiz eta ikusmen arren, ezin dugu dagoeneko Esango ez da hori ez da izango. Nahi dugu ziur algoritmo hau egiteko izango da, hain zuzen ere, oraindik ere, nolabait ere, lan eta ez bakarrik utzi digu begizta infinitua bat trabatuta. 

Beraz, zein da urrats lehen? Kalkulatu erdigunea Gaur egungo array. Zer da erdigunea Gaur egungo array? Beno, 7, ezta? 14 plus 0 2 banatuta 7 da. 15 zer bilatzen ari gara? No. Nahiko hurbil, baina begira ari gara balio bat baino zertxobait handiagoa da. 

Beraz, badakigu dela joan izan ezerezetik 15 ezkerreko. Helburu baino handiagoa da zer erdigunea ere egin. Eta beraz, hasteko puntua berria ezarri dugu erdi-erdian eskubidea izan. Erdigunea da gaur egun 7, hain demagun the Irteeran berria 8 da. Eta zer eraginkorrean dugu Berriro egiten da bazterrera utzi the array osoan ezkerreko erdi. 

Orain, berriz diogu du prozesatu denbora gehiago. Kalkulatu erdigunea berria. 8 plus 14 22 da, 2 11 da banatuta. 23 zer bilatzen ari gara? Zoritxarrez, ez. Gaude balio bat bilatzen 23 baino gutxiago. Eta, beraz, kasu honetan, goazen amaieran puntua aldatzeko zuzena izateko uneko erdigunea ezkerreko. Egungo erdigunea 11 da, eta beraz, bukaera puntua berriak ezarri beharko dugu hurrengo denbora joan ginen 10 Prozesu honen bidez. 

Berriz ere, berriro prozesuan zehar joan ginen. Kalkulatu erdigunea. 8 plus 10 2 banatuta 9 da. 19 zer bilatzen ari gara? Zoritxarrez, ez. Oraindik ari gara bila Zenbaki bat baino gutxiago. Beraz, une honetan amaiera puntua aldatu egingo besterik erdigunea ezkerreko izan. Erdigunea da gaur egun 9 beraz, azken puntua 8 izango da. Eta orain, besterik bilatzen ari gara elementu array bakar batean. 

Zer da array honen erdigunea? Beno, hasten 8 at da, 8 amaitzen da, erdigunea 8 da. Hori da guk nahi? Ari gara 17k? Ez, 16. bilatzen ari gara. Beraz, badago sorta batean bazaude, nonbait existitu behar da non gaur egun gauden ezkerreko. Beraz, zer egin behar dugu joan? Beno, ezarri egingo dugu amaieran puntu besterik ez izan uneko erdigunea ezkerreko. Beraz, ez dugu azken puntua aldatu egingo 7ra. Ez zer besterik ikusten duzu Hemen gertatu zen, nahiz eta? Look up hemen orain. 

Start bukaera baino handiagoa da orain. Eraginkortasunez, bi muturrak gure array zeharkatu dute, eta Irteeran da orain amaieran puntua ondoren. Beno, hori ez da Edozein zentzurik, ezta? Beraz, orain, zer esan dezakegu dugu tamaina 0 array azpi dute. Eta behin goaz ahaztuak Puntu honetan, gaur egun ezin dugu elementu hori bermatzen 16 ez du array existitzen, Irteeran delako eta amaieran puntu zeharkatu dute. Eta, beraz, ez da han. Orain, nabarituko hori da apur bat the Irteeran eta amaiera baino ezberdinak puntu berdina izanik. Dugu izan balitz bila 17an, izango litzateke array, eta hasiera-puntua izan eta amaitzeko, azken iterazio duten puntua puntu horiek zeharkatu aurretik, aurkitu izana genuke 17 han. Besterik ez da, zeharkatuko dute, ahal dugun elementua ez du bermatzen array existitzen. 

Hargatik hartu en asko gutxiago bilaketa lineala baino urrats. Txarrenean ere, izan dugu zatitu n elementu zerrenda bat behin eta berriz erditik helburua bilatzen, bai delako helburu elementua nonbait izango da, azken batean zatiketa, edo ez du existitzen. Beraz, kasu txarrenean, izan dugu zatitu array du dakizu? N aldiz log; dugu arazoa moztu dute erdi aldiz kopuru jakin batean. Aldiz kopuru hori log n da. 

Zer da kasurik onenean? Beno, lehenengo aldiz dugu erdigunea kalkulatzeko, zer bilatzen ari gara aurkitzen dugu. Aurreko guztietan bilaketa bitarra adibide besterik ez dugu desagertu baino gehiago izan badugu bila elementua 15, berehala topatu ditugun litzateke. Hori oso hasiera-hasieratik izan zen. Hori izan zen erdigunea split batean lehen saiakera bilaketa bitarra zatiketa baten. 

Eta beraz txarrenean Kasu, bilaketa bitarra exekutatzen log n, hau da, nabarmen hobea Bilaketa lineala, txarrena kasuan baino. Kasurik onenean ere, binary Bilaketa-1 omega exekutatzen. Beraz, bilaketa bitarra asko da bilaketa lineala baino hobea, baina prozesua landu behar duzula sailkatuz, zure array lehenengo ahal duzun aurretik leverage bilaketa bitarra boterea. 

Naiz Doug Lloyd. Hau CS 50 da.