>> ROB Bowden: Hola, sóc Rob.
Com ens emprem una recerca binària?
Anem a veure.
Per tant, tingueu en compte que aquesta recerca ens anem per aplicar de forma recursiva.
Vostè podria també posar en pràctica la recerca binària iterativa, pel que si es va fer,
que està perfectament bé.
>> Ara primer, recordem el que el paràmetres de cerca estan destinats a ser.
Aquí, veiem valor int, que és suposa que és el valor que l'usuari és
buscant.
Veiem la matriu valors int, que és la matriu en la qual estem
la recerca de valor.
I veiem int n, que és la durada de la nostra matriu.
>> Ara, primer el primer.
Verifiquem si n és igual a 0, en aquest cas tornem falsa.
Això és només dir si tenim un buit matriu, el valor no és clara en un
matriu buida, pel que pot tornar false.
>> Ara, en realitat volem fer el binari Cerca part de recerca binària.
Per tant, volem trobar el mitjà element d'aquesta matriu.
Aquí, diem mitjana és igual a n dividida per 2, ja que l'element mitjà és
serà la longitud d' nostra matriu dividida per 2.
Ara anem a comprovar per veure si el element mitjà és igual al valor que estem
buscant.
Així que si els valors de mitjana és igual a valor, pot retornar cert ja que trobem el
valor a la nostra matriu.
>> Però si això no era cert, ara hem de fer el recursiva
pas de cerca binària.
Hem de buscar o bé a la esquerra de la matriu o de la
centre de la matriu.
Així que aquí, diem si els valors en el medi és menys del seu valor, això significa que el valor
va ser major que la meitat de la matriu.
Així que el valor ha de ser el de la dreta de la element que acabem de veure.
>> Així que aquí, anem a buscar de forma recursiva.
I anem a veure el que estem passant a aquest en un segon.
Però anem a buscar la dreta de l'element mitjà.
I en l'altre cas, el que significa que valor va ser de menys de la meitat de la
matriu, i així anem per buscar a l'esquerra.
Ara, l'esquerra serà una mica més fàcil de veure.
Així, veiem aquí que estem recursiva trucant recerca on la primera
argument és, de nou, el valor estem mirant per sobre.
El segon argument serà el matriu que buscàvem acabat.
I l'últim element actual és mitjà.
Recordeu que l'últim paràmetre és la nostra int n, de manera que aquesta és la durada de la nostra matriu.
>> A la crida recursiva a buscar, estem ara dient que la longitud de la
array és mitjà.
Per tant, si la nostra matriu era de mida 20 i buscat en l'índex 10, ja que al mig és
20 dividit entre 2, això significa que estem passar 10 com la nova
longitud de la nostra matriu.
Recordeu que quan vostè té una matriu de longitud 10, això significa que la validesa
els elements estan en els índexs de 0 a 9.
Així que això és exactament el que volem especificar la nostra gamma actualitzada - l'esquerra
matriu des de l'element mitjà.
>> Així que, mirant cap a la dreta és una mica més difícil.
Ara en primer lloc, anem a considerar la longitud de la matriu a la dreta de la
element mitjà.
Per tant, si la nostra matriu era de grandària n, llavors el nova matriu serà de grandària n menys
almenys la meitat gener.
Per tant, anem a pensar en n menys mig.
>> Un cop més, si la matriu van ser de mida 20 i dividim per 2 per obtenir el mitjà,
de manera que el mitjà és 10, llavors n almenys mig ens donarà el 10, així que 10
elements a la dreta del centre.
Però també tenim la menys 1, ja que no volem
incloure el propi medi.
Llavors n almenys mitja menys 1 ens dóna la nombre total d'elements a la dreta
l'índex mitjà de la matriu.
>> Ara aquí, recordar que el medi paràmetre és la matriu de valors.
Així que aquí, estem passant una actualitzat array valors.
Això a més dels valors, més mitjà 1 és dient realment recursiva anomenada
recerca, passant per una nova matriu, on que la nova matriu comença en el medi
més un de la nostra sèrie els valors originals.
>> Una sintaxi alternativa perquè, ara que que ha començat a veure els punters, és
valors ampersand més mitjana 1.
Així, pren la direcció del centre a més d'un element dels valors.
>> Ara, si vostè no estava còmode modificació d'una sèrie com aquesta,
També podria haver implementat aquesta usant una funció auxiliar recursiva, on
funció auxiliar que pren més arguments.
Així que en lloc de prendre només el valor, matriu, i la mida de la matriu,
la funció auxiliar podria prendre més arguments, inclosos l'índex més baix
que a vostè li preocupen a la matriu i l'índex superior que es preocupa
sobre la matriu.
>> I així no perdre de vista tant de la menor índex i l'índex superior, que no ho fan
s'hagi de modificar mai la valors originals matriu.
Vostè només pot seguir utilitzar la matriu de valors.
Però aquí, notem que no necessitem un ajudant funcionar, sempre que estiguem
disposats per modificar l'original valors d'array.
Estem disposats a passar 01:00 valors actualitzats.
>> Ara, no podem recerca binària sobre una matriu que és classificar.
Així que anem a obtenir aquesta resolt.
Ara, observi que tipus és les dues i paràmetres int valors, que és el
matriu que estem ordenar i int n, que és la longitud de la matriu que
estem ordenació.
Així doncs, aquí volem implementar un algorisme d'ordenació
és a dir o de n al quadrat.
Vostè pot optar per l'ordenació de bombolla, la selecció tipus, o l'ordenació per inserció, o
algun altre tipus que no tenim vist a classe.
Però aquí, anem a utilitzar la selecció de gènere.
>> Per tant, repetirem sobre tota la matriu.
Bé, aquí veiem que estem iterant de 0 a n almenys 1.
Per què no tot el camí fins al n?
Bé, si ja hem va solucionar la primera N almenys 1 elements, llavors el
últim element del que ja ha de ser en el lloc correcte, de manera que la classificació més
tota la matriu.
>> Ara, recorda com la selecció tipus d'obres.
Anem a repassar tota la matriu buscant el valor mínim
la matriu i el pal que al principi.
A continuació repassarem tota la array de nou a la recerca de la segona
element més petit, i el pal que en la segona posició en el
matriu, i així successivament.
Llavors, això és el que està fent.
>> Aquí, estem veient que estem establint el mínim actual
valor per a l'índex i.
Així que en la primera iteració, anem considerar el valor mínim per ser
el començament de la nostra matriu.
Llavors, repetirem l' resta de la gamma, verificant
veure si hi ha algun element més petit que la qual estem actualment
tenint en compte el mínim.
>> Així que aquí, els valors j més un - que és menys del que som en l'actualitat
tenint en compte el mínim.
Llavors anem a actualitzar el que creiem que és el mínim per
índex j més 1.
Per tant, fer que a través de tota la matriu, i després d'aquest bucle, mínim
ha de ser l'element mínim de la posició i-èsima de la matriu.
>> Un cop tinguem això, podem intercanviar la valor mínim en la posició i-èsima
en la matriu.
Així que això és només un intercanvi estàndard.
Nosaltres guardem en un valor temporal - el valor i-èsim de la matriu -
posat en el valor i-èsim de la matriu de la valor mínim que pertany allà,
i després emmagatzemar de nou on el valor mínim actual que solia ser el
i-èsim valor de la matriu, de manera que que no ens perdem.
>> Així, que continua en la següent iteració.
Anem a començar a buscar el segon valor mínim i que publicarà al
segona posició.
A la tercera iteració, buscarem el tercer valor mínim i l'insert
que en la tercera posició, i així fins que tenim una matriu ordenada.
El meu nom és Rob, i això era una mena de selecció.