Rob BOWDEN: Hi, Ako Rob. Paano nagpapatupad kami ng isang binary paghahanap? Ng malaman Hayaan. Kaya, tandaan na ang paghahanap na ito kami ay pagpunta ipatupad recursively. Maaari mo ring ipatupad ang binary paghahanap iteratively, kaya kung ginawa mo iyon, na perpektong fine. 

Unang Ngayon, ni tandaan ipaalam kung ano ang mga parameter sa paghahanap ay nilalayong maging. Dito, makikita natin halaga int, na dapat na maging ang halaga gumagamit ay naghahanap para sa. Nakakakita kami ng mga halaga int array, na ay ang array na kung saan kami ay naghahanap ng mga halaga. At nakita namin int n, na ang haba ng aming array. 

Ngayon, ang unang bagay na unang. Nagsusuri kami upang makita kung n ay katumbas ng 0, sa kung saan bumalik kami ng hindi totoo. Na lang sinasabi kung kami ay may isang walang laman array, halaga ay malinaw na hindi sa isang Walang laman ang array, upang maaari naming ibalik hindi totoo. 

Ngayon, gusto talaga naming gawin ang binary bahagi ng paghahanap ng binary paghahanap. Kaya, nais naming hanapin ang gitna elemento ng array. Dito, sinasabi namin gitna katumbas n hinati sa pamamagitan ng 2, dahil sa gitna elemento ay pagpunta sa maging ang haba ng ang aming array na hinati sa 2. Ngayon kami ay pagpunta sa suriin upang makita kung ang gitnang elemento ay katumbas ng halaga Ikinalulungkot namin naghahanap para sa. Kaya kung halaga gitna ay katumbas ng halaga, namin Maaari nagbabalik ng tunay na dahil nakita namin ang halaga sa aming array. 

Ngunit kung iyon ay hindi totoo, ngayon kailangan namin upang gawin ang recursive hakbang ng binary paghahanap. Kailangan namin upang maghanap alinman sa iniwan ng array o sa gitna ng array. Kaya dito, sinasabi namin kung halaga sa gitna ay mas mababa sa halaga, na nangangahulugan na halaga ay mas mataas kaysa sa gitna ng array. Kaya dapat sa kanan ng ang halaga elemento na tumingin lang namin sa. 

Kaya dito, kami ay pagpunta sa maghanap recursively. At titingnan namin kung ano kami ay pagpasa upang ito sa isang segundo. Ngunit kami ay pagpunta upang maghanap sa kanan ng gitna ng elemento. At sa iba pang mga kaso, ay nangangahulugan na na halaga ay mas mababa kaysa sa gitna ng array, at sa gayon kami ay pagpunta upang maghanap sa kaliwa. Ngayon, sa kaliwa ay magiging medyo mas madali upang tumingin sa. Kaya, makikita natin dito na hindi namin recursively pagtawag kung saan ang unang paghahanap argumento ay, muli, ang halaga naghahanap kami ng mahigit. Ang pangalawang argumento ay magiging ang array na tayo ay naghahanap sa ibabaw. At ang huling elemento ang gitnang ngayon. Tandaan ang huling parameter ay ang aming int n, kaya iyon ang haba ng aming array. 

Sa recursive tawag upang maghanap, hindi namin ngayon na nagsasabi na ang haba ng array ay gitna. Kaya, kung ang aming array ay ng laki 20 at kami Naghanap sa index 10, dahil gitna ay 20 na hinati sa 2, na nangangahulugan na namin pagpasa sa 10 bilang bagong haba ng aming array. Tandaan na kapag mayroon kang isang array ng haba 10, ay nangangahulugan na ang wastong mga elemento ay nasa mga indeks ng 0 hanggang 9. Kaya ito ay kung ano mismo ang gusto naming tukuyin ang aming na-update array - kaliwa array mula sa gitna ng elemento. 

Kaya, naghahanap sa kanan ay medyo mas mahirap. Unang Ngayon, isaalang-alang na ang haba ipaalam ng array sa kanan ng gitna ng elemento. Kaya, kung ang aming array ay ng laki n, pagkatapos ay ang bagong array ay magiging ng laki n minus gitna minus 1. Kaya, sa tingin ng n minus gitna ipaalam. 

Muli, kung ang array ay ng laki 20 at hinati namin sa pamamagitan ng 2 upang makuha ang gitna, kaya sa gitna ay 10, pagkatapos n minus gitna ay pagpunta sa bigyan kami ng 10, kaya 10 mga elemento sa kanan ng gitna. Ngunit mayroon din namin ito minus 1, dahil hindi namin nais na Kasama sa gitna mismo. Kaya n minus gitna minus 1 ay nagbibigay sa amin ang kabuuang bilang ng mga elemento sa kanan ng gitna index sa array. 

Ngayon dito, tandaan na ang gitna parameter ay ang mga halaga ng array. Kaya dito, naka-pagpasa kami ng isang na-update na mga halaga ng array. Ang mga halaga plus gitna plus 1 ay talagang sinasabi recursively tumawag paghahanap, ang pagpasa sa isang bagong array, kung saan na ang mga bagong array ay nagsisimula sa gitna plus isa sa aming mga orihinal na halaga ng array. 

Isang kahaliling syntax para sa na, ngayon na sinimulan mo upang makita ang mga payo, ay mga halaga ng ampersand gitna plus 1. Kaya, grab ng address ng gitnang plus ang isang elemento ng mga halaga. 

Ngayon, kung ikaw ay hindi komportable pagbabago ng isang array tulad ng na, ikaw maaari ring nagpatupad ito gamit isang recursive function na lingkod, kung saan na lingkod function na tumatagal higit pang mga argumento. Kaya sa halip ng pagkuha lamang ang halaga, ang array, at sa laki ng array, ang lingkod ng function ay maaaring tumagal nang higit pa mga argument, kabilang ang mas mababang index na nais mong mag-intindi sa array at ang itaas na index na mahalaga sa iyo tungkol sa array. 

At kaya pagpapanatiling track ng parehong mga mas mababang index at itaas na index, hindi mo gusto kailangan upang kailanman baguhin ang orihinal na halaga ng array. Maaari mo lamang patuloy na gamitin ang mga halaga ng array. Ngunit dito, mapapansin hindi namin kailangan ang isang lingkod aandar hanggat hindi namin payag upang baguhin ang orihinal mga halaga ng array. Kami ay handa upang pumasa sa isang na-update na mga halaga. 

Ngayon, hindi namin maaari binary paghahanap sa paglipas ng isang array na ay unsorted. Kaya, sabihin makakuha ng ito pinagsunod-sunod out. Ngayon, mapapansin na ang uri ay nakalipas na dalawang mga parameter int value, kung saan ay ang array na aming pag-uuri, at int n, kung saan ay ang haba ng array na kami ay pag-uuri. Kaya, dito gusto naming ipatupad isang pag-uuri algorithm na o ng n nakalapat. Maaari kang pumili ng bubble sort, seleksyon -uri-uriin, o uri pagpapasok, o ilang iba pang mga uri mayroon kaming hindi nakikita sa klase. Ngunit dito, kami ay pagpunta sa gamitin uriin pagpili. 

Kaya, kami ay pagpunta upang umulit sa ibabaw ng buong array. Well, dito makita namin na kami ay iterating mula 0 hanggang n minus 1. Bakit hindi lahat ng mga paraan ng hanggang sa n? Well, kung na pinagsunod-sunod na namin ang unang n minus 1 elemento, pagkatapos ay ang napaka huling elemento kung ano ang dapat na maging sa tamang lugar, kaya pag-uuri sa ibabaw ang buong array. 

Ngayon, tandaan kung paano seleksyon uri gumagana. Kami ay pagpunta sa pumunta sa buong array naghahanap para sa minimum na halaga sa ang array at stick na sa simula. Pagkatapos kami ay pagpunta sa pumunta sa ibabaw ng buong array muli naghahanap para sa ikalawang pinakamaliliit na elemento, at stick na sa pangalawang posisyon sa array, at iba pa. Kaya, na kung ano ito ay ginagawa. 

Dito, kami ay nakakakita na kami pag-set ang kasalukuyang minimum na ng halaga sa i-ika-index. Kaya sa unang iteration, kami ay pagpunta upang isaalang-alang ang minimum na halaga na maging simula ng aming array. Pagkatapos, kami ay pagpunta upang umulit sa ibabaw ng natitira sa array, pagsuri sa makita kung mayroong anumang mga elemento na mas maliit sa ang isa na hindi namin kasalukuyan kung isasaalang-alang ang minimum. 

Kaya dito, mga halaga, values ​​j plus isa - iyon mas mababa kaysa sa kung ano tayo sa kasalukuyan kung isasaalang-alang ang minimum. Pagkatapos kami ay pagpunta sa i-update ang ano sa tingin namin ay ang minimum na index j plus 1. Kaya, gawin iyon sa buong array, at pagkatapos na ito para sa loop, minimum ay dapat na ang minimum na elemento mula sa ang posisyon i-ika sa array. 

Sa sandaling mayroon kaming na, maaari naming magpalit ang minimum na halaga sa i-ika-posisyon sa array. Kaya ito ay lamang ng isang standard na swap. Nag-iimbak kami sa isang pansamantalang halaga - ang halaga i-ika sa array - Nailagay ang halaga i-ika sa array ang minimum na halaga na pag-aari doon, at pagkatapos ay mag-imbak pabalik sa kung saan ang kasalukuyang minimum na halaga na ginamit upang maging ang ika-i halaga sa array, kaya na hindi namin ginawa mawala ito. 

Kaya, na patuloy sa sa susunod na pag-ulit. Sisimulan naming naghahanap para sa ikalawang minimum na halaga at ipasok iyon sa pangalawang posisyon. Sa ikatlong-ulit, titingnan namin para sa ang ikatlong minimum na halaga at insert na papunta sa pangatlong posisyon, at iba pa sa hanggang mayroon kaming pinagsunod-sunod ng array. Ang pangalan ko ay Rob, at ito ay uri pagpili.