>> 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.