ROB BOWDEN: Hoi, ik ben Rob. Hoe kunnen we gebruik van een binary search? Laten we eens kijken. Dus, er rekening mee dat deze zoekopdracht gaan we recursief uitvoeren. Je zou binary search ook uitvoering iteratief, dus als je dat deed, dat is prima. 

Nu laten we eerst eens herinneren wat de parameters te zoeken zijn bedoeld om te worden. Hier zien we int waarde, die moet de waarde de gebruiker zijn zoekt. We zien de int waarden array, die is de array waarin we op zoek naar waarde. En we zien int n, dat is de lengte van onze array. 

Nu, het eerste wat eerst. Wij controleren om te zien of n gelijk is aan 0, in welk geval we return false. Dat is gewoon te zeggen als we een leeg array waarde duidelijk niet per lege array, dus we kunnen return false. 

Nu, we eigenlijk willen de binaire doen zoek een deel van binaire zoeken. Dus, we willen naar het midden te vinden element van deze array. Hier zeggen we midden gelijk aan n verdeeld met 2, aangezien het middelste element naar de lengte zijn van ons aanbod gedeeld door 2. Nu gaan we om te controleren om te zien of de middelste element is gelijk aan de waarde die wij zijn zoekt. Dus als waarden midden gelijk waarde, we waar kan terugkeren omdat we vonden de waarde in onze array. 

Maar als dat niet zo was, nu moeten we de recursieve doen stap van binary search. We moeten ofwel zoeken naar de links van de matrix of de midden van de array. Dus hier, zeggen we als waarden op midden is minder dan de waarde, dat wil zeggen dat de waarde was groter dan het midden van de array. Dus moet waarde aan de rechterkant van de element dat we gewoon gekeken. 

Dus hier gaan we naar zoeken recursief. En kijken we naar wat we passeren deze in een tweede. Maar we gaan zoeken naar de rechts van het middelste element. En in het andere geval, dat betekent dat waarde lager dan het midden van de was array, en dus we gaan te zoeken naar links. Nu, de linker gaat worden een stuk makkelijker om naar te kijken. Zo zien we hier dat we recursief waar de eerste bellen zoekopdracht argument weer, de waarde we kijken voorbij. Het tweede argument gaat worden de array die we op zoek waren voorbij. En het laatste element is nu midden. Denk aan de laatste parameter is onze int n, dus dat is de lengte van ons aanbod. 

In de recursieve oproep om te zoeken, we zijn nu dat de lengte van de array is midden. Dus, als ons aanbod was van maat 20 en we gezocht bij index 10, sinds midden is 20 gedeeld door 2, dat betekent dat we 10 langs de nieuwe lengte van onze array. Vergeet niet dat als je een array lengte 10, dat betekent de geldige elementen in indices 0 tot 9. Dus dit is precies wat we willen specificeren onze vernieuwde serie - links matrix van het midden element. 

Dus, op zoek naar de juiste is een beetje moeilijker. Nu laten we eerst eens kijken naar de lengte van de matrix rechts van de middelste element. Dus, als ons aanbod was van grootte n, dan is de nieuwe array van grootte n minus zijn midden minus 1. Dus, laten we denken aan n minus midden. 

Ook als de array waren van grootte 20 en we delen door 2 naar het midden te krijgen, dus het midden is 10, dan is n minus midden gaat om ons 10, dus 10 elementen rechts van het midden. Maar we hebben ook dit minus 1, omdat we niet willen onder het midden zelf. Zo n minus midden minus 1 geeft ons de totale aantal elementen rechts de middelste index in de array. 

Nu hier, bedenk dan dat het midden parameter waarden matrix. Dus hier, we passeren een bijgewerkte waarden array. Deze waarden plus midden plus 1 is eigenlijk zeggen recursief bellen zoeken, passeren in een nieuwe array, waar dat nieuwe array begint in het midden plus een van onze oorspronkelijke waarden array. 

Een alternatieve syntax voor dat, nu je bent begonnen met pointers te zien, is ampersand waarden midden plus 1. Dus, pak het adres van de middelste plus een element van waarden. 

Nu, als je niet comfortabel het wijzigen van een array als dat, je kon ook hebben geïmplementeerd dit met behulp van een recursieve helper functie, waarbij dat helper functie neemt meer argumenten. Dus in plaats van alleen de waarde, de matrix en de grootte van de matrix, de helper functie kan langer duren argumenten, waaronder de lagere index dat je over zou geven in de array en de bovenste index die u geeft over de array. 

En dus het bijhouden van zowel de lagere index en de hogere index, u niet moet ooit wijzigen de oorspronkelijke waarden array. Je kunt gewoon blijven Gebruik de waarden array. Maar hier zien we geen helper nodig functioneren zolang we bereid om het origineel te wijzigen waarden array. We zijn bereid om in de pas een bijgewerkte waarden. 

Nu kunnen we niet binary search boven een array die is ongesorteerd. Dus, laten we dit uitgezocht. Merk nu op dat soort is afgelopen twee parameters int waarden, die de array die we sorteren en int n, dat de lengte van de array die we sorteren. Dus, hier willen we de uitvoering van een sorteer-algoritme die o n kwadraat. Je kon bubble sort, selectie kiezen sorteren of insertion sort of een ander soort hebben we niet gezien in de klas. Maar hier, we gaan Gebruik selectie sorteren. 

Dus, we gaan herhalen over de gehele array. Nou, hier zien we dat we itereren van 0 tot n minus 1. Waarom niet de hele weg tot aan n? Nou, als we al naargelang de eerste n minus 1 elementen, vervolgens de laatste element wat er al moeten zijn op de juiste plaats, zodat het sorteren op de hele array. 

Nu bedenk hoe selectie sort werkt. We gaan te gaan over de hele array zoekt de minimale waarde de array en stok die aan het begin. Dan gaan we te gaan over de gehele serie opnieuw op zoek naar de tweede kleinste element, en stok, die in de tweede positie in de matrix, enzovoort. Dus, dat is wat dit doet. 

Hier, we zien dat we het instellen van de huidige minimale waarde voor de i-de index. Dus op de eerste iteratie, we gaan overwegen de minimumwaarde te het begin van ons aanbod. Dan gaan we itereren over de rest van de array te controleren zien of er elementen kleiner dan degene die we momenteel gezien de minimale. 

Dus hier, waarden j plus een - dat is minder dan wat we momenteel gezien de minimale. Dan gaan we werken wat we denken dat is het minimum om index j plus 1. Dus doen over de hele array, en na deze lus, minimum moet de minimale element van het i-de positie in de array. 

Zodra we dat, kunnen we ruilen de minimale waarde in de i-de positie in de array. Dus dit is gewoon een standaard swap. We slaan in een tijdelijke waarde - de i-de waarde in de matrix - steken in de i-de waarde in de matrix de minimumwaarde dat er behoort, en vervolgens op te slaan terug naar waar het stroom gebruikt om de te minimumwaarde i-de waarde in de matrix, zodat dat we niet verliezen. 

Zo, die nog steeds op de volgende iteratie. We gaan op zoek naar de tweede minimumwaarde en steek die in de tweede positie. Op de derde iteratie, zullen we kijken naar de derde minimale waarde en insert dat naar de derde positie, en dus op tot we een gesorteerde array. Mijn naam is Rob, en dit was selectie sorteren.