ROB BOWDEN: Hei, jeg er Rob. Hvordan kan vi ansette en binær søk? La oss finne det ut. Så, merk at dette søket skal vi å gjennomføre rekursivt. Du kan også implementere binære søk iterativt, så hvis du gjorde det, det er helt greit. 

Nå først, la oss huske hva parametere for å søke er ment å være. Her ser vi int verdi, som er ment å være den verdien brukeren søker etter. Vi ser int verdier array, som er matrisen der er vi søker etter verdi. Og vi ser int n, som er lengden på rekken. 

Nå, første først. Vi sjekker for å se om n er lik 0, i hvilket tilfelle vi return false. Det er bare å si at hvis vi har en tom array, verdien er åpenbart ikke i en tom array, slik at vi kan returnere false. 

Nå, vi faktisk ønsker å gjøre det binære søk del av binære søk. Så ønsker vi å finne midten element i denne matrise. Her sier vi midt lik n delt med 2, siden midten element er kommer til å være lengden vårt spekter delt på to. Nå skal vi sjekke for å se om midtre element tilsvarer verdien vi er søker etter. Så hvis verdier midten lik verdi, vi kan returnere sant siden vi fant verdi i vårt utvalg. 

Men hvis det ikke var sant, nå vi trenger for å gjøre den rekursive trinn av binære søk. Vi trenger å søke enten til venstre for matrisen eller til midten av tabellen. Så her sier vi om verdier på midten er mindre enn verdien, det betyr at verdi var større enn i midten i matrisen. Så verdien må være til høyre for element som vi bare så på. 

Så her, vi kommer til å søke rekursivt. Og vi vil se på hva vi passerer til dette i et sekund. Men vi kommer til å søke til høyre for midtelementet. Og i det andre tilfellet, det betyr at -verdien var lavere enn midten av array, og så skal vi å søke til venstre. Nå, er venstre kommer til å bli litt lettere å se på. Så ser vi her at vi er rekursivt ringer søk der først argumentet er, igjen, verdien vi ser over. Det andre argumentet kommer til å være det array som vi skulle søke over. Og det siste elementet er nå midten. Husk den siste parameteren er vår int n, slik at det er lengden på rekken. 

I den rekursive kall til å søke, vi er nå si at lengden av matrise er midten. Så, hvis vår rekke var av størrelse 20, og vi søkte på indeksen 10, siden midten er 20 delt på to, betyr at vi er passerer 10 som ny lengden på array. Husk at når du har en matrise av lengde 10, betyr at den gyldige elementene er i indeksene 0 til 9. Så dette er akkurat hva vi ønsker å spesifisere vår oppdaterte utvalg - venstre matrisen fra det midtre element. 

Så, ser til høyre er litt vanskeligere. Nå først, la oss vurdere lengden i matrisen til høyre for midterste element. Så, hvis vår rekke var av størrelse n, deretter nye utvalget vil være av størrelse n minus midten minus en. Så, la oss tenke på n minus midten. 

Igjen, dersom matrisen var av størrelse 20 og Vi deler med 2 for å få midten, så midten er 10, deretter n minus midten kommer til å gi oss 10, så 10 elementer til høyre for midten. Men vi har også denne minus 1, siden vi ikke ønsker å inkludere midten selv. Så n minus midten minus 1 gir oss totalt antall elementer til høyre av midten indeksen i matrisen. 

Nå her, husk at midten parameter er verdiene array. Så her er vi passerer en oppdaterte verdier array. Dette verdier pluss midten pluss en er faktisk sier rekursivt ringe søk, passerer i en ny rekke, der den nye matrisen begynner i midten pluss en av vår opprinnelige verdier array. 

En alternativ syntaks for det, nå som du har begynt å se pekere, er Ampersand verdier midten pluss en. Så, ta tak i adressen til midten plus en del av verdier. 

Nå, hvis du ikke var komfortable modifisere en matrise som det, du kunne også ha implementert dette ved hjelp en rekursiv hjelpefunksjon, der som hjelper funksjon tar flere argumenter. Så i stedet for å ta akkurat den verdien, matrisen og størrelsen av matrisen, hjelperen funksjonen kunne ta mer argumentasjon, inklusive lavere indeks at du ville bry seg om i matrisen og den øvre indeksen at du bryr deg om matrisen. 

Og så holder styr på både lavere indeksen og den øvre indeks, gjør du ikke trenger å stadig endre opprinnelige verdiene array. Du kan bare fortsette å bruke verdiene array. Men her ser vi ikke trenger en hjelper fungere så lenge vi er villig til å modifisere den opprinnelige verdier array. Vi er villig til å passere i en oppdatert verdier. 

Nå kan vi ikke binære søk på en matrise som er usortert. Så, la oss få dette sortert ut. Nå merker den slags er forbi to parametre int verdier, som er den array som vi sortering, og int n, som er lengden av den matrise som vi sortering. Så, her vi ønsker å implementere en sorteringsalgoritme som er o av n squared. Du kan velge boble sortere, valg sorter eller innsetting sortere, eller noen annen form vi ikke har sett i klassen. Men her skal vi bruke valget slag. 

Så vi kommer til å reagere over hele matrisen. Vel, her ser vi at vi gjentar fra 0 til n minus en. Hvorfor ikke hele veien opp til n? Vel, hvis vi allerede har sortert den første n minus 1 elementer, deretter den aller siste element hva må allerede være på riktig sted, slik at sortering løpet hele utvalget. 

Nå husker hvordan valg Sorter fungerer. Vi kommer til å gå over hele matrisen ser for minimumsverdien i matrisen og pinne som i begynnelsen. Så får vi kommer til å gå over hele matrise igjen på jakt etter den andre minste element, og pinne som i den andre stilling i matrise, og så videre. Så, det er hva dette gjør. 

Her ser vi at vi er sette gjeldende minste Verdien til den i-te indeks. Så på den første iterasjon, skal vi å vurdere minimumsverdien til å være starten av våre array. Deretter kommer vi til å iterere over Resten av matrisen, å kontrollere se om det ikke noe element som er mindre enn den som vi er nå med tanke på minimum. 

Så her, verdier j pluss én - det er mindre enn hva vi er i dag med tanke på minimum. Så skal vi oppdatere hva vi tror er minimum for å indeksen j pluss en. Så, gjør det over hele matrisen, og etter denne for sløyfen, minimum bør være minimum elementet fra i-te posisjonen i matrisen. 

Når vi har det, kan vi bytte minimumsverdi inn i i-te posisjon i matrisen. Så dette er bare en standard swap. Vi lagrer i en midlertidig verdi - i-te verdien i matrisen - satt inn i den i-te verdi i matrisen i minimumsverdi som hører til der, og deretter lagre tilbake til der værende minimumsverdi som brukes for å være den i-te verdi i matrisen, slik at at vi ikke mister det. 

Så, som fortsetter på neste iterasjon. Vi vil begynne å lete etter den andre minimumsverdi, og sett det inn i andre stilling. På den tredje iterasjon, vil vi se etter den tredje minimumsverdi og innsats at i den tredje posisjonen, og så på før vi har en sortert array. Mitt navn er Rob, og dette var valg liksom.