ROB BOWDEN: Hej, jag är Rob. Hur vi använder en binär sökning? Låt oss ta reda på. Så, notera att sökningen ska vi att genomföra rekursivt. Du kan också implementera binär sökning iterativt, så om du gjorde det, det är väl bra. 

Nu först, låt oss komma ihåg vad parametrar till sökningen är tänkt att vara. Här ser vi int värde, vilket är tänkt att vara det värde användaren är efter. Vi ser int värden arrayen, vilket är arrayen där vi är söker efter värde. Och vi ser int n, vilket är längden på vår array. 

Nu, först sak först. Vi kontrollerar om n är lika med 0, i vilket fall vi returnera false. Det är bara att om vi har en tom array värde är uppenbarligen inte i en tom array, så att vi kan returnera false. 

Nu, vi faktiskt vill göra det binära Sök del av binär sökning. Så, vi vill hitta mitt inslag i denna samling. Här säger vi mitt lika n delas genom två, sedan mitten elementet är kommer att vara längden på vår samling delat med 2. Nu ska vi kontrollera om det mellersta del är lika med värdet vi är efter. Så om värden mitten lika värde, vi kan returnera sant eftersom vi hittat värde i vår samling. 

Men om det inte var sant, nu vi behöver göra den rekursiva steget med binär sökning. Vi måste söka antingen till kvar i matrisen eller till den mitten av uppsättningen. Så här säger vi om värden vid mitten är mindre än värdet, innebär att det värdet var större än den mellersta av arrayen. Så värdet måste vara till höger om den faktor som vi bara tittade på. 

Så här kommer vi att sök rekursivt. Och ska vi titta på vad vi passerar till detta i en sekund. Men vi kommer att söka till höger om den mellersta elementet. Och i det andra fallet, innebär det att värde var lägre än i mitten av array, och så ska vi att söka till vänster. Nu är den vänstra kommer att vara lite lättare att titta på. Så ser vi här att vi är rekursivt ringer ökning där den första argumentet är, återigen, det värde vi ser över. Det andra argumentet är att vara den array som vi sökte över. Och det sista elementet är nu mitt. Kom ihåg att den sista parametern är vår int n, så det är längden på vår samling. 

I rekursivt anrop för att söka, vi är nu säga att längden av den array är mitt. Så, om vår samling var i storlek 20 och vi sökte på index 10, eftersom mitt är 20 delat med 2, gör att vi är passerar 10 som ny längden på vår array. Kom ihåg att när du har en array med längd 10, innebär att den giltiga elementen är i index 0 till 9. Så det här är precis vad vi vill specificera vår uppdaterade samling - vänster array från mittelementet. 

Så, titta till höger är lite svårare. Nu först, låt oss betrakta längden av uppsättningen till höger om den mellanelementet. Så, om vår array var av storlek n, då ny samling kommer att vara av storlek n minus mitt minus 1. Så, låt oss tänka på n minus mitten. 

Återigen, om matrisen var av storlek 20 och vi delar med 2 för att få en mitt, så i mitten är 10, då n minus mitten kommer att ge oss 10, så 10 element till höger om mitten. Men vi har också denna minus 1, eftersom vi inte vill inkluderar mitten självt. Så n minus mitten minus 1 ger oss totala antalet element till höger av mitt index i arrayen. 

Nu här, kom ihåg att mitt parametern är värden array. Så här, vi passerar en uppdaterade värden array. Dessa värden plus mitt plus 1 är faktiskt säger rekursivt ringa sök, som passerar i en ny array, där att ny array börjar i mitten plus en av våra ursprungliga värden array. 

En alternativ syntax för det, nu när du har börjat se pekare, är et-värden mitten plus ett. Så, ta adressen till den mellersta plus en del av värden. 

Nu, om du inte var bekväm modifiera en matris som detta, du kunde också ha genomfört detta med en rekursiv hjälparfunktion, där att hjälparfunktion tar fler argument. Så i stället för att bara värde, desto array, och storleken på matrisen, hjälpare funktion skulle ta mer argument, bland annat lägre index att du skulle bry sig om i arrayen och den övre index att du bryr dig om uppsättningen. 

Och så hålla reda på både den nedre index och den övre index, gör du inte behöver någonsin ändra ursprungliga värdena array. Du kan bara fortsätta att använda värden array. Men här, märker vi inte behöver en hjälpare fungera så länge som vi är villig att ändra den ursprungliga värden array. Vi är villiga att gå in en uppdaterad värden. 

Nu kan vi inte binär sökning över en array som är osorterade. Så, låt oss få detta redas ut. Nu märker det slaget är förbi två parametrar int värden, som är den array som vi sorterar, och int n, vilken är längden av den matris som vi sortering. Så här vill vi att genomföra en sorteringsalgoritm som är o n i kvadrat. Du kan välja bubbla sortera, val sortera eller inser sortera eller någon annan form har vi inte ses i klassen. Men här kommer vi till använda val sort. 

Så kommer vi att iterera över hela antenn. Tja, här ser vi att vi iteration från 0 till n minus 1. Varför inte hela vägen upp till n? Tja, om vi redan har sorterat det första n minus 1 element, då den mycket sista elementet vad måste redan vara på rätt plats, så sortering över hela arrayen. 

Nu, kom ihåg hur urvalet sorterings fungerar. Vi kommer att gå över hela antenn söker det minsta värdet i matrisen och stick som vid början. Sen ska vi gå över hela array igen efter den andra minsta elementet, och stick som i den andra positionen i array, och så vidare. Så, det är vad det gör. 

Här ser vi att vi är inställning av nuvarande minimi värde till den i: te indexet. Så på den första iterationen, vi ska att överväga minimivärdet att vara början av vår samling. Sedan kommer vi att iterera över återstoden av arrayen, kontrollera för att se om det några element som är mindre än det som vi är idag med tanke på den minsta. 

Så här värderar j plus en - det är mindre än vad vi är idag med tanke på den minsta. Sen ska vi uppdatera vad vi tycker är det minsta till index j plus en. Så, gör det över hela matrisen, och efter detta for-loop, minimum bör vara det minsta elementet från den i: te positionen i arrayen. 

När vi har det, kan vi byta minimivärde i den i: te positionen i arrayen. Så det här är bara en vanlig swap. Vi lagrar i ett tillfälligt värde - det i: te värdet i matrisen - sätta i den i: te värdet i matrisen den minimivärde som hör hemma där, och sedan lagra tillbaka in där nuvarande minimivärde brukade vara i: te värdet i matrisen, så att vi inte förlorar det. 

Så fortsätter det på nästa iteration. Vi kommer att börja leta efter den andra lägsta värdet och sätt in det i andra positionen. På tredje iteration, kommer vi att titta efter den tredje minsta värde och insats som i den tredje positionen, och så på tills vi har en sorterad array. Mitt namn är Rob, och detta var val sort.