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 van soort, die sorteert de array genoemd waarden. Dus laten we zoeken te pakken. 

Zoeken wordt momenteel geïmplementeerd als een lineair zoeken. Maar je kunt veel beter dan dat. Lineair zoeken is in O n geïmplementeerd tijd, die is vrij langzaam, hoewel kan naar 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 een naald, en in dit Bijvoorbeeld, het gehele getal 3. 

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 0. 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 3 Onze naald is 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 rechter gebonden kan draai de zoeken grenzen slechts een klein beetje meer, enzovoort enzovoort, totdat je je naald te vinden. 

Dus wat doet de pseudo code eruit? Nou, nu we nog altijd kijken door de lijst en hebben nog steeds elementen om te kijken in, nemen we de middelste van de lijst en dat vergelijken middelste waarde voor 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 return false u. Omdat de naald zeker is niet in de hooiberg. 

Nu, een keurige ding over dit pseudo code in binary search 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 bestrijken een beetje later in de cursus. Maar weet wel dat het een optie is als je wilt proberen.