[Muziek] 

ZAMYLA CHAN: Het eerste wat je zou bericht over vondst is dat we al hebben code geschreven voor ons. Dit heet verdeelsleutel. Zodat we niet alleen het schrijven van onze eigen coderen van kras meer. Integendeel, we vullen de holtes in sommige reeds bestaande code. 

De status van huidige map programma vraagt ​​voor getallen om de hooiberg te vullen, zoekt het hooiberg voor een gebruiker ingediend naald, en doet dit door te bellen naar soort en zoeken, functies gedefinieerd in helpers.c. Dus status van huidige map is al geschreven. Jouw taak is om helpers te schrijven. 

Dus wat doen we? We implementeren twee functies. Zoek geeft true als een waarde is te vinden in de hooiberg, terugkerende false als de waarde is niet in de hooiberg. En dan zijn we ook de uitvoering sorteren die sorteert de array genoemd waarden. 

Dus laten we zoeken te pakken. Zoeken wordt momenteel geïmplementeerd als een lineaire zoeken, maar je kunt veel doen beter dan dat. Lineair zoeken is in O geïmplementeerd n tijd, dat is heel traag. Hoewel, het kan zoeken elke lijst gegeven. Jouw taak is om binary search uit te voeren, die tijd O van log n heeft gelopen. Dat is behoorlijk snel. 

Maar er is een bepaling. Binary search kunt alleen zoeken door voorgesorteerd lijsten. Waarom is dat? 

Nou laten we eens kijken naar een voorbeeld. Gegeven een matrix met waarden, de hooiberg, we gaan op zoek voor een naald. En in dit voorbeeld het gehele getal drie. De manier waarop binary search werkt is dat Vergelijken we de middelste waarde van de array om de naald, net als hoe we een telefoonboek geopend voor het midden pagina in week nul. 

Dus na de middelste waarde te vergelijken met de naald, kunt u weggooien ofwel de linker of de rechter helft van de array door aanscherping van je grenzen. In dit geval, aangezien drie onze naald, minder dan 10, de middelste waarde, de recht gebonden kan verminderen. Maar probeer je grenzen te maken zo strak mogelijk. Als de middelste waarde is niet de naald, dan weet je dat je niet hoeft te opnemen in uw zoekopdracht. Dus je hebt gelijk gebonden kan draai de zoeken grenzen slechts een klein beetje meer, en zo verder en zo voort totdat je je naald te vinden. 

Dus wat doet de pseudocode eruit? Goed, terwijl we nog steeds op zoek via de lijst en hebben nog elementen aan kijk in, nemen we het midden van de lijst, en vergelijk die middelste waarde aan onze naald. Als ze gelijk zijn, dan betekent dat we hebben vond de naald en we kunnen return true. 

Anders, als de naald is minder dan de middelste waarde, dan betekent dat we kan de rechter helft weggooien, en gewoon zoek de linkerzijde van de array. Anders zullen we zoeken in de rechterzijde van de array. En aan het eind, als je die niet hebt meer elementen overgelaten om te zoeken, maar je nog niet gevonden je naald, dan moet je return false omdat de naald zeker niet in de hooiberg. 

Nu een nette ding over deze pseudocode binair zoeken is dat het kan worden geïnterpreteerd als een iteratief of recursieve implementatie. Dus het zou recursieve zijn als je geroepen de zoekfunctie binnen de zoekopdracht werken aan elke helft van de array. We zullen recursie een beetje later in de dekking natuurlijk, maar weet wel dat het een optie als u wilt proberen. 

Laten we nu eens kijken naar soort. Sorteren neemt een array en het integer n, dat is de grootte van de matrix. Nu zijn er verschillende soorten van soorten, en je kunt kijken naar een aantal shorts voor demo's en uitleg. Het type rendement voor onze sorteerfunctie is nietig. Dus dat betekent dat we niet gaan aan een reeks terug van soort. We zijn eigenlijk gaan naar de zeer veranderen array die werd doorgegeven aan ons. 

En dat is mogelijk omdat arrays zijn bij verwijzing doorgegeven in C. Nu zullen we Bekijk meer over dit later, maar de wezenlijk verschil tussen het voorbijgaan in iets als een integer en passerende in een array, is dat wanneer je passeren in een geheel getal, is C gewoon gaan maak een kopie van die integer en doorgeven het aan de functie. De oorspronkelijke variabele wordt niet gewijzigd zodra de functie is beëindigd. Met een matrix, anderzijds, het niet van plan om een ​​kopie te maken, en je zult daadwerkelijk het bewerken van de zeer serie zelf. 

Dus een soort soort is de selectie sorteren. De selectie sorteren werkt door te beginnen bij het begin, en dan herhalen over en vinden het kleinste element. En dan moet je ruilen dat kleinste element met het eerste. En dan moet je naar het tweede element Zoek de volgende kleinste element, en dan wisselen die met de tweede element in de array, omdat Het eerste element is al gesorteerd. En dus dan blijven je voor elke element identificeren het kleinste waarde en het ruilen het uit. 

Want ik gelijk is aan 0, het eerste element om n minus 1, je gaat om te vergelijken elke volgende waarde na dat en vinden de index van de minimale waarde. Zodra je de minimale waarde-index, kun je die waarde van de array te ruilen minimum en serie I. 

Een ander type van soort dat je kunt implementeren is bubble sort. Dus bubble sort doorloopt de lijst vergelijken van aangrenzende elementen en omwisselen van de elementen die zijn in de verkeerde volgorde. En zo, de grootste element zal bubble tot het einde. En de lijst wordt eenmaal niet meer gesorteerd elementen zijn verwisseld. 

Dus dat zijn twee voorbeelden van sorteren algoritmen die u kunt uitvoeren voor de vondst programma. Zodra u klaar bent met sorteren, en je hebt gedaan zoeken, je bent klaar. Mijn naam is Zamyla, en dit is CS50. 

[Muziek]