>> ROB BOWDEN: Bună, eu sunt Rob.
Cum putem folosi o căutare binar?
Haideți să aflăm.
Deci, rețineți că această căutare vom pentru punerea în aplicare recursiv.
Ai putea să pună în aplicare, de asemenea, de căutare binară iterativ, așa că, dacă ai făcut asta,
asta e foarte bine.
>> Acum, în primul rând, să ne amintim ceea ce parametri de căutare sunt menite să fie.
Aici, vom vedea valoare int, care este ar trebui să fie valoarea utilizatorul este
căutați.
Vedem matrice valori int, care este matrice în care suntem
în căutare de valoare.
Și vom vedea int n, care este lungimea matrice noastre.
>> Acum, primul lucru primul.
Vom verifica pentru a vedea dacă n este egal cu 0, în caz în care ne vom întoarce false.
Asta e doar că dacă avem un gol matrice, o valoare nu este în mod clar într-o
array gol, astfel încât să putem întoarce false.
>> Acum, am de fapt vrei sa faci binar Cautare parte din căutare binare.
Deci, ne-o dorim pentru a găsi mijlocul element al acestei matrice.
Aici, noi spunem de mijloc este egal cu n împărțit de 2, întrucât elementul din mijloc este
Va fi lungimea gama noastră împărțit la 2.
Acum vom verifica pentru a vedea dacă elementul din mijloc este egal cu valoarea suntem
căutați.
Deci, dacă valorile de mijloc este egal cu valoare, avem poate reveni adevărat, deoarece am găsit
valoare în gama noastră.
>> Dar în cazul în care nu era adevărat, acum avem nevoie pentru a face recursiv
pas de căutare binare.
Avem nevoie de a căuta fie la a plecat de matrice sau la
mijloc de matrice.
Deci, aici, ne spune dacă valorile de la mijloc este mai puțin decât valoarea, ceea ce înseamnă că valoarea
a fost mai mare decât la mijloc de matrice.
Deci, valoarea trebuie să fie de dreapta a element care ne-am uitat la.
>> Deci, aici, vom căutare recursiv.
Și ne vom uita la ceea ce ne trece la aceasta într-o secundă.
Dar vom căuta la dreapta a elementului de mijloc.
Și în celălalt caz, ceea ce înseamnă că valoare a fost mai mică decât la mijlocul
matrice, și așa vom pentru a căuta spre stânga.
Acum, stânga va fi un pic mai ușor să se uite la.
Deci, vedem aici că suntem recursiv de asteptare de căutare în cazul în care primul
argument este, din nou, valoarea căutăm peste.
Al doilea argument va fi matrice care ne-au fost căutați peste.
Și ultimul element este acum de mijloc.
Amintiți-vă de ultimul parametru este int nostru n, așa că e lungimea de matrice noastre.
>> În apelul recursiv pentru a căuta, suntem acum spunând că lungimea
matrice este de mijloc.
Deci, în cazul în care gama noastră era de mărimea 20 și ne-am căutat la index de 10, deoarece de mijloc este
20 împărțit la 2, înseamnă că suntem trecerea 10 ca noul
lungime de matrice noastre.
Amintiți-vă că atunci când aveți o matrice de lungime 10, ceea ce înseamnă că valabil
elemente sunt în indici de la 0 la 9.
Deci, asta este exact ceea ce vrem să specifica gama noastră actualizare - stânga
matrice de elementul de mijloc.
>> Deci, în căutarea de la dreapta este un pic mai dificil.
Acum, în primul rând, să ia în considerare lungimea de matrice la dreapta a
element de mijloc.
Deci, în cazul în gama noastră a fost de dimensiune n, atunci Noua matrice va fi de dimensiune n minus
minus mijloc 1.
Deci, haideți să ne gândim de n minus de mijloc.
>> Din nou, în cazul în matrice au fost de mărime 20 și vom împărți cu 2 pentru a obține mijloc,
astfel încât la mijloc este de 10, atunci n minus de mijloc este de gând să ne dea 10, deci 10
elemente de la dreptul de mijloc.
Dar avem, de asemenea, acest minus 1, deoarece nu vrem să
includ mijloc în sine.
Deci, n minus de mijloc minus 1 ne dă numărul total de elemente de la dreapta
indicelui de mijloc în matrice.
>> Acum, aici, amintiți-vă că la mijloc parametru este array valori.
Deci, aici, vom trece un actualizat valori matrice.
Aceste valori, plus plus de mijloc 1 este de fapt spunând apel recursiv
căutare, trecerea într-o nouă matrice, în cazul în care că noua matrice începe în mijloc
plus una din valorile originale gama noastră.
>> O sintaxă alternativă pentru că, acum că ați început să vadă indicii, este
Valorile ampersand plus de mijloc 1.
Deci, apuca adresa de mijloc plus un element de valori.
>> Acum, dacă nu sunt confortabile modificarea o matrice de genul asta, ai
de asemenea, ar putea fi pus în aplicare acest lucru utilizând o functie helper recursiv, unde
că funcția helper ia mai multe argumente.
Deci, în loc de a lua doar valoarea, matrice, și dimensiunea matricii,
funcția de ajutor ar putea lua mai mult argumente, inclusiv indicele inferior
care le-ar pasa de la matrice și indicele de sus ca iti pasa
despre matrice.
>> Și așa a ține evidența atât de jos index și indicele de sus, tu nu faci
necesitatea de a modifica oricând valorile originale matrice.
Puteți continua doar pentru a folosi matrice valori.
Dar aici, observa nu avem nevoie de un ajutor funcționează atâta timp cât suntem
dispus să modifice originalul Valorile matrice.
Suntem dispuși să treacă în un valori actualizate.
>> Acum, nu putem binar de căutare pe o matrice care este nesortate.
Deci, hai să sortate.
Acum, observați că este un fel trecut două Parametrii int valori, care este
matrice care suntem sortarea, și int n, care este lungimea unui array care
suntem de sortare.
Deci, aici vrem să pună în aplicare un algoritm de sortare
adică o de n pătrat.
Ai putea alege cu bule de sortare, selectare un fel, sau inserare fel, sau
un alt fel noi nu avem văzut în clasă.
Dar aici, vom folosesc selecție de sortare.
>> Deci, vom repeta pentru întreaga rețea.
Ei bine, aici vom vedea că suntem iterarea de la 0 la n minus 1.
De ce nu tot drumul până la n?
Ei bine, dacă ne-am sortate deja primul n minus 1 elemente, apoi
ultimul element de care trebuie să fie deja în locul corect, așa sortare peste
întreaga rețea.
>> Acum, amintiți-vă cât de selecție un fel de lucrări.
Vom merge pentru întreaga rețea, în căutarea pentru valoarea minimă în
matrice și stick-ul care la început.
Apoi vom trece peste întreaga matrice din nou în căutarea pentru a doua
mai mic element, și băț că în cea de a doua poziție în
matrice, și așa mai departe.
Deci, asta e ceea ce acest lucru este de a face.
>> Aici, vedem că suntem stabilirea minim actual
valoare a indicelui i-lea.
Deci, pe prima iterație, vom să ia în considerare valoarea minimă a fi
începutul matrice noastre.
Apoi, vom repeta de-a lungul restul de matrice, de verificare a
a se vedea dacă există orice elemente mai mici decât cel pe care suntem în prezent
considerând minim.
>> Deci, aici, valorile j plus una - care este mai puțin decât ceea ce sunt în prezent
considerând minim.
Apoi, vom actualiza ceea ce noi credem ca este minim a
index j plus 1.
Deci, nu că pe întreaga rețea, și după aceasta pentru buclă, minim
ar fi elementul minim din poziția i-lea în matrice.
>> După ce ne-am asta, putem schimba Valoarea minimă în poziția i-lea
în matrice.
Deci, aceasta este doar un schimb standard.
Stocăm într-o valoare temporar - valoarea i-lea în matrice -
pune în valoare i-lea în matrice Valoarea minimă care aparține acolo,
și apoi depozitați înapoi în cazul în care Valoarea minimă de curent folosit pentru a fi
i-lea valoare în matrice, așa pe care nu l-am pierdut.
>> Deci, care continuă pe urmatoarea iteratie.
Vom începe căutarea pentru al doilea valoarea minimă și introduceți că în
a doua poziție.
La a treia repetare, ne vom uita pentru a treia valoarea minimă și inserția
care în poziția a treia, și așa pe până când vom avea un tablou sortat.
Numele meu este Rob, și acest lucru a fost un fel de selecție.