ROB BOWDEN: Hi, jien Rob. Kif aħna jimpjegaw tfittxija binarja? Ejja nsib. Allura, innota li dan tfittxija aħna qed tmur biex jimplimentaw recursively. Inti tista 'wkoll timplimenta tfittxija binarja iteratively, hekk jekk inti ma dan, li perfettament multa. 

Issa l-ewwel, ejja niftakru dak l- parametri ta 'tiftix huma intenzjonati li jkunu. Hawnhekk, naraw valur int, li hija suppost ikunu l-valur l-utent huwa tiftix għal. Naraw l-array valuri int, li hija l-array li aħna qed tiftix għall-valur. U naraw int n, li hija it-tul ta 'firxa tagħna. 

Issa, l-ewwel ħaġa l-ewwel. Aħna tikkontrolla biex tara jekk n ikun egwali għal 0, b'mod f'liema każ nerġgħu lura falza. Li jinsab biss qal jekk għandna vojt firxa, il-valur huwa b'mod ċar mhux fi array vojta, sabiex inkunu nistgħu ritorn foloz. 

Issa, aħna fil-fatt tixtieq li tagħmel il-binarju parti tfittxija tat-tfittxija binarja. Għalhekk, irridu isibu l-nofs element ta 'din array. Hawnhekk, irridu ngħidu nofs ugwali n maqsuma bi 2, peress li l-element tan-nofs huwa se jkun it-tul ta ' firxa tagħna diviż bil 2. Issa aħna qed tmur biex tikkontrolla biex tara jekk l- element nofs huwa ugwali għall-valur nkunu tiftix għal. Mela jekk valuri nofs ugwali valur, aħna jistgħu jirritornaw veru peress li sibna l- valur fil-firxa tagħna. 

Imma jekk dan ma kienx veru, issa għandna bżonn biex jagħmlu l-rikursivi pass ta 'tfittxija binarja. Għandna bżonn li tfittex jew lill- xellug tal-firxa jew l- nofs tal-firxa. So here, ngħidu jekk il-valuri fil-nofs huwa inqas mill-valur, dan ifisser li l-valur kienet akbar minn-nofs tal-firxa. Allura valur għandu jkun li d-dritt tal- element li aħna biss ħares lejn. 

Allura hawn, aħna qed tmur biex tfittxija recursively. U aħna ser tħares lejn dak li aħna qed tgħaddi għal dan fit-tieni. Iżda aħna qed tmur biex tfittex għall- lemin tal-element tan-nofs. U fil-każ ieħor, dan ifisser li valur kien inqas minn-nofs tal- array, u hekk aħna qed tmur biex tfittex lejn ix-xellug. Issa, ix-xellug se tkun daqsxejn aktar faċli li tħares lejn. Allura, naraw li aħna hawnhekk qed recursively ssejjaħ tfittxija fejn l-ewwel argument huwa, għal darb'oħra, il-valur aħna qed tfittex fuq. It-tieni argument se tkun l- array li konna tiftix fuq. U l-aħħar element huwa issa nofs. Ftakar l-aħħar parametru huwa int tagħna n, b'tali mod li t-tul ta 'firxa tagħna. 

Fis-sejħa rikursivi li persuna tfittex, aħna qed issa tgħid li t-tul tal- firxa hija nofs. Għalhekk, jekk firxa tagħna kienet ta 'daqs 20 u aħna mfittxija fil-indiċi 10, peress tan-nofs huwa 20 diviż bi 2, dan ifisser li aħna qed tgħaddi 10 bħala l-ġdid tul ta 'firxa tagħna. Ftakar li meta inti għandek firxa ta 'tul ta' 10, dan ifisser l valida elementi huma indiċi 0 sa 9. Allura dan huwa eżattament dak li rridu tispeċifika firxa aġġornata tagħna - fuq ix-xellug array mill-element nofs. 

Għalhekk, tħares lejn il-lemin hija daqsxejn aktar diffiċli. Issa l-ewwel, ejja jikkunsidraw it-tul ta 'l-array għad-dritt ta' l- element nofs. Għalhekk, jekk firxa tagħna kienet ta 'daqs n, allura l- firxa ġdida se tkun ta 'minus daqs n minus nofs 1. Allura, ejja jaħsbu n-nofs minus. 

Għal darb'oħra, jekk il-firxa kienu ta 'daqs 20 u aħna iddividi 2 li jiksbu l-tan-nofs, hekk-nofs huwa ta '10, allura n nieqes nofs se tagħtina 10, hekk 10 elementi għad-dritt ta 'nofs. Iżda għandna wkoll dan minus 1, peress li aħna ma rridux li jinkludu l-nofs innifsu. Allura n minus nofs minus 1 jagħtina l- numru totali ta 'elementi lejn il-lemin ta 'l-indiċi tan-nofs fil-firxa. 

Issa hawnhekk, ftakar li l-nofs parametru huwa l-array valuri. Allura hawn, aħna qed jgħaddu minn aġġornata valuri array. Dan valuri plus plus nofs 1 tkun attwalment qal recursively sejħa tfittxija, li jgħaddi fil-firxa ġdida, fejn li array ġdid jibda fin-nofs plus wieħed mill-valuri oriġinali firxa tagħna. 

Sintassi sostitut għal dan, issa li inti stajt beda biex tara pointers, huwa Valuri ampersand plus nofs 1. Allura, grab-indirizz tat-nofs plus element wieħed tal-valuri. 

Issa, jekk inti ma kinux komdi timmodifika firxa bħal dik, inti tista 'wkoll implimentaw dan bl-użu funzjoni helper jirrikorri, fejn dik il-funzjoni helper jieħu aktar argumenti. Allura minflok tieħu biss il-valur, l- array, u d-daqs tal-array, il-funzjoni helper tista 'tieħu aktar argumenti, inkluż l-indiċi t'isfel li inti jimpurtak fil-firxa u l-indiċi ta 'fuq li inti kura dwar il-firxa. 

U hekk iżżomm rekord ta 'kemm l-aktar baxx indiċi u l-indiċi ta 'fuq, inti ma jeħtieġ li qatt timmodifika l- valuri oriġinali array. Tista 'biss tibqa' jużaw il-firxa valuri. Iżda hawnhekk, avviż li ma kellniex bżonn helper jiffunzjonaw sakemm aħna qed lesti li timmodifika l-oriġinali valuri array. Aħna lesti li jgħaddu AN valuri aġġornati. 

Issa, ma nistgħux tfittxija binarja fuq firxa li mhux magħżul. Allura, ejja nikseb dan mifthiema. Issa, avviż li sort huwa żewġ passat parametri int valuri, li hija l- array li aħna qed issortjar, u int n, li huwa t-tul tal-firxa li aħna qed issortjar. Allura, hawn irridu li jimplimentaw algoritmu issortjar dan huwa o ta n kwadru. Inti tista 'tagħżel it-tip bubble, l-għażla sort, jew sort inserzjoni, jew xi tip ieħor aħna ma jidhru fil-klassi. Iżda hawnhekk, aħna qed tmur biex jużaw sort għażla. 

Allura, aħna qed tmur biex jtenni fuq il-firxa sħiħa. Well, hawn naraw li aħna qed mtennija minn 0 sa n minus 1. Għaliex ma-triq kollha sa n? Ukoll, jekk aħna stajt diġà magħżula l-ewwel n nieqes 1 elementi, allura l- ħafna aħħar element dak li għandu jkun diġà fil-post korrett, hekk issortjar fuq l-array kollu. 

Issa, tiftakar kif selezzjoni sort xogħlijiet. Aħna qed tmur biex jmorru fuq il-firxa sħiħa tfittex l-valur minimu fil- il-firxa u stick li fil-bidu. Allura aħna qed tmur biex jmorru fuq il-kollu firxa darb'oħra tfittex għat-tieni element iżgħar, u stick li fit-tieni pożizzjoni fil- firxa, u l-bqija. Allura, dak hu li dan qed tagħmel. 

Hawnhekk, aħna qed jaraw li aħna qed iffissar tal-minimu attwali valur għall-indiċi i-th. Allura fuq l-ewwel iterazzjoni, aħna qed tmur li tikkunsidra l-valur minimu li jkun il-bidu ta 'firxa tagħna. Imbagħad, aħna qed tmur biex jtenni fuq il- bqija tal-firxa, il-verifika biex ara jekk hemm xi elementi iżgħar minn il-wieħed li aħna qed bħalissa jikkunsidraw il-minimu. 

So here, valuri j plus wieħed - li inqas minn dak li aħna bħalissa jikkunsidraw il-minimu. Imbagħad aħna qed tmur biex taġġorna dak aħna naħsbu li hija l-minimu li indiċi j plus 1. Allura, jagħmlu dan madwar l-firxa sħiħa, u wara dan għal loop, minimu għandu jkun l-element minima minn il-pożizzjoni i-th fil-firxa. 

Ladarba għandna dan, nistgħu tpartit l- valur minimu fil-pożizzjoni i-th fil-firxa. Allura din hija biss tpartit standard. Aħna jaħżen fil-valur temporanju - il-valur i-th fil-firxa - tqiegħed fil-valur i-th fil-firxa tal- valur minimu li jappartjeni hemmhekk, u mbagħad aħżen lura fil fejn il- valur minimu kurrenti użati biex ikunu l- Valur i-th fil-array, hekk li aħna ma titilfu. 

Allura, li tkompli fuq l-iterazzjoni li jmiss. Aħna ser tibda tfittex għall-tieni valur minimu u daħħal li fil- tieni pożizzjoni. Fit-tielet iterazzjoni, aħna ser tfittex it-tielet valur minimu u daħħal li fit-tielet pożizzjoni, u għalhekk fuq sakemm għandna firxa Issortjati. Jisimni Rob, u dan kien sort għażla.