ZAMYLA CHAN: Die eerste ding wat jy dalk kennisgewing oor vonds is dat ons reeds het 'n kode geskryf vir ons. Dit is die verspreiding kode genoem. So ons is nie net die skryf van ons eie kode van nuuts af nie. Inteendeel, is ons in te vul die leemtes in 'n paar pre-bestaande kode. 

Die find.c program vra vir nommers die hooiberg te vul, soek die hooiberg vir 'n gebruiker voorgelê naald, en doen dit deur te bel soort en Soek, funksies gedefinieer in helpers.c. So find.c is reeds geskryf. Jou werk is om helpers te skryf. 

So, wat doen ons? Ons is die uitvoering van twee funksies. Soek, wat terugkeer waar as 'n waarde word gevind in die hooiberg, terugkeer valse indien die waarde is nie in die hooiberg. En dan is ons ook die implementering van aard, wat allerhande die skikking met die naam waardes. So laat se pak soek. 

Soek tans geïmplementeer as 'n lineêre soek. Maar jy kan nie veel beter as dit. Lineêre soektog in O N geïmplementeer tyd, wat baie stadig, maar dit kan soek enige gegewe lys om dit te. Jou werk is om binêre soek om te implementeer, wat loop tyd O log n. Dit is redelik vinnig. 

Maar daar is 'n bepaling. Binêre soek kan net soek deur pre-gesorteer lyste. Hoekom is dit? Wel, laat ons kyk na 'n voorbeeld. Gegewe 'n verskeidenheid van waardes, die hooiberg, ons gaan om te kyk vir 'n naald, en in hierdie Byvoorbeeld, die heelgetal 3. 

Die manier waarop binêre soek werk, is dat ons die middelste waarde van vergelyk die skikking aan die naald, baie soos hoe Ons maak 'n telefoon boek na die middel bladsy in Week 0. So na die middelste waarde te vergelyk die naald, kan jy weggooi óf die linker-of die regter helfte van die skikking deur strenger jou perke. In hierdie geval, sedert 3, ons naald, is minder as 10, die middelste waarde, die reg gebind kan verminder. 

Maar probeer om jou grense te maak so styf as moontlik. As die middelste waarde is nie die naald, dan moet jy weet dat jy nie nodig het om te sluit dit in jou soektog. So jou reg gebind kan draai die Soek perke net 'n klein bietjie meer, en so aan en so voort, totdat jy jou naald. 

So, wat nie die pseudo kode lyk? Wel, terwyl ons nog steeds deur die lys en nog elemente om te kyk in, neem ons die middel van die lys en vergelyk dit Midde-waarde aan ons naald. As hulle gelyk is, dan beteken dit dat ons het het gevind dat die naald, en ons kan terug waar. 

Andersins, as die naald is minder as Die middelste waarde is, dan beteken dit dat ons kan die regter helfte weggooi en net soek die linkerkant van die skikking. Andersins, sal ons soek die regterkant van die skikking. En aan die einde, as jy het nie meer elemente links te soek, maar jy nog nie jou naald gevind nie, dan moet jy terugkeer, vals is. Omdat die naald beslis is nie in die hooiberg. 

Nou, 'n netjiese ding oor hierdie pseudo kode in binêre soek is, is dat dit kan geïnterpreteer word as óf 'n iteratiewe of rekursiewe implementering. So is dit rekursiewe sou wees as jy genoem die soek funksie binne die soektog funksioneer op óf die helfte van die skikking. Ons sal dek rekursie 'n bietjie later in die kursus. Maar weet dat dit is 'n opsie As jy wil om te probeer.