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.