>> ROB BOWDEN: Hej, jeg er Rob.
Hvordan kan vi ansætte en binær søgning?
Lad os finde ud af.
Så bemærk, at denne søgning vil vi at gennemføre rekursivt.
Du kan også gennemføre binær søgning iterativt, så hvis du gjorde det,
det er helt fint.
>> Nu først, lad os huske på, hvad parametre til søgningen er beregnet til at være.
Her ser vi int værdi, hvilket er formodes at være den værdi, brugeren er
søger efter.
Vi ser int værdier array, som er den matrix, som vi er
søger efter værdi.
Og vi ser int n, som er længden af ​​vores array.
>> Nu første først.
Vi tjekker for at se, hvis n er lig med 0, i hvilket tilfælde vi vender tilbage falsk.
Det er bare at sige, hvis vi har en tom array, værdien er helt klart ikke et
tom array, så vi kan vende tilbage falsk.
>> Nu vi faktisk ønsker at gøre den binære søgning del af binær søgning.
Så vi ønsker at finde den midterste element i denne matrix.
Her siger vi midt lig n delt med 2, idet den midterste element er
vil være længden af vores matrix divideres med 2.
Nu skal vi til at tjekke for at se, om midterste element lig med den værdi, vi er
søger efter.
Så hvis værdier midten er lig værdi, vi kan returnere sandt, da vi fandt
værdi i vores array.
>> Men hvis det ikke var sandt, nu vi nødt til at gøre den rekursive
trin i binær søgning.
Vi er nødt til at søge til enten den venstre for matrix eller til
midten af ​​arrayet.
Så her, siger vi, hvis værdier i midten er mindre end værdien, der betyder, at værdien
var større end den midterste af matrixen.
Så værdi skal være til højre for element, som vi lige har set på.
>> Så her, vi kommer til at søg rekursivt.
Og vi vil se på, hvad vi passerer til dette i en anden.
Men vi kommer til at søge til ret af den midterste element.
Og i det andet tilfælde, der betyder, at værdien var mindre end i midten af
array, og så vil vi at søge til venstre.
Nu er venstre vil være lidt nemmere at se på.
Så vi ser her, at vi er rekursivt ringer søgning, hvor den første
argument er, igen, værdien vi kigger forbi.
Det andet argument vil være den array, vi søger forbi.
Og det sidste element er nu midten.
Husk den sidste parameter er vores int n, så det er længden af ​​vores array.
>> I det rekursive kald til at søge, er vi siger nu, at længden af ​​den
array er midten.
Så hvis vores vifte var størrelse 20 og vi søgte på indeks 10, da midten er
20 divideret med 2, der betyder, at vi passerer 10 som den nye
længden af ​​vores array.
Husk, at når du har en array af længde 10, betyder det gyldige
elementer er i indeks 0 til 9.
Så dette er præcis, hvad vi ønsker at specificere vores opdaterede array - venstre
matrix fra midten element.
>> Så ser til højre er en smule mere vanskeligt.
Nu først, lad os overveje længden af arrayet til højre for
midterste element.
Så hvis vores vifte var størrelse n, så nyt array vil være af størrelse n minus
midterste minus 1.
Så lad os tænke på n minus midten.
>> Igen, hvis matrixen var størrelse 20 og vi dividere med 2 for at få midten,
så midten er 10, så n minus midten vil give os 10, så 10
elementer til højre for midten.
Men vi har også denne minus 1, da vi ikke ønsker at
omfatte midten selv.
Så n minus midten minus 1 giver os samlede antal elementer til højre
af den midterste indeks i array.
>> Nu her huske på, at den midterste parameter er værdier array.
Så her er vi passerer en opdaterede værdier array.
Denne værdier plus midterste plus 1 er faktisk siger rekursivt kalde
søgning, der passerer i en ny matrix, hvor at nyt array starter i midten
plus én af vores oprindelige værdier array.
>> En alternativ syntaks for, at nu hvor du er begyndt at se pegepinde, er
Ampersand værdier midterste plus 1.
Så tag fat i adressen på den midterste plus en del af værdier.
>> Nu, hvis du ikke var komfortable modificere et array som, du
kunne også have gennemført denne hjælp en rekursiv hjælpefunktion, hvor
at hjælperen funktion tager flere argumenter.
Så i stedet for at tage bare den værdi, array, og størrelsen af ​​array,
den hjælpefunktion kunne tage mere argumenter, herunder lavere indeks
at du ville bekymre sig om i array og den øvre indeks, som du holder af
om array.
>> Og så holde styr på både den lave indekset og øvre indeks, behøver du ikke
nødt til nogensinde ændre oprindelige værdier array.
Du kan bare fortsætte med at bruge værdierne array.
Men her, bemærker vi ikke brug for en hjælper fungere, så længe vi er
villig til at ændre den oprindelige værdier array.
Vi er villige til at passere i en opdaterede værdier.
>> Nu kan vi ikke binær Søg igen et array, der er usorteret.
Så lad os få dette løst.
Nu bemærke, at slags er forbi to parametre int værdier, som er
array, vi sortering og int n, som er længden af ​​array,
vi sortering.
Så her vi ønsker at gennemføre en sorteringsalgoritme
der er o n potens.
Du kan vælge boble sortere, udvælgelse sortere, eller indsættelse slags, eller
nogle andre slags vi ikke har set i klassen.
Men her, vi kommer til at bruge udvælgelse slags.
>> Så vi kommer til at gentage over hele systemet.
Nå, her ser vi, at vi iteration fra 0 til n minus 1.
Hvorfor ikke hele vejen op til n?
Tja, hvis vi allerede har sorteret det første n minus 1 elementer, så
meget sidste element, hvad allerede skal på det rigtige sted, så sortering i
hele systemet.
>> Nu huske, hvordan valg slags virker.
Vi kommer til at gå over hele systemet udkig efter den mindste værdi på
array og stok, der i begyndelsen.
Så vi kommer til at gå over hele matrix igen på udkig efter den anden
mindste element, og stok, der i den anden position i
array, og så videre.
Så det er, hvad det gør.
>> Her ser vi, at vi er sætte den nuværende minimum
værdi for den i'te indeks.
Så på den første iteration, vil vi at undersøge den mindste værdi for at være
starten af ​​vores array.
Så vi kommer til at gentage over den resten af ​​arrayet, kontrol for
se, om der nogen elementer mindre end den ene, som vi i øjeblikket
overvejer minimum.
>> Så her, værdier j plus én - det er mindre end hvad vi er i øjeblikket
overvejer minimum.
Så vi kommer til at opdatere hvad vi synes er minimum for at
indeks j plus 1.
Så gør det på tværs af hele array, og efter denne for-løkke, minimum
bør være det mindste element fra den i'te position i arrayet.
>> Når vi har det, kan vi bytte mindste værdi i den i'te position
i array'et.
Så dette er blot en standard swap.
Vi gemmer i en midlertidig værdi - den i'te værdi i array -
sat i den i'te værdi i array minimumsværdi, der hører der,
og derefter gemme tilbage til hvor nuværende minimum værdi plejede at være
i'te værdi i matrixen, så at vi ikke mister den.
>> Så det fortsætter på den næste iteration.
Vi vil begynde at lede efter den anden mindste værdi og indsætte det i
anden position.
På den tredje iteration, vil vi se efter den tredje mindste værdi og indsæt
der ind i tredje position, og så på, indtil vi har en sorteret array.
Mit navn er Rob, og dette var valg slags.