ZAMYLA CHAN: Prva stvar, ki jo morda obvestilo o najdbi je, da smo že so zapisana koda za nas. To se imenuje porazdelitev koda. Torej ne samo pisanje lastnega kodo iz nič več. Namesto tega smo zapolnjevanje praznin v nekaterih obstoječo kodo. 

Program find.c vpraša po številkah zapolniti senu, išče senu uporabniško predložiti iglo, in to počne tako, da kliče vrste in iskanja, funkcije so opredeljena V helpers.c. Torej je find.c napisal že. Vaša naloga je, da napišete pomočnice. 

Torej, kaj počnemo? Mi smo za izvajanje dveh funkcij. Iskanje, ki vrne true, če vrednost se nahaja v senu, vračanje false, če je vrednost ne v senu. In potem smo tudi izvajanje vrste, ki sortira array imenovano vrednosti. Torej, kaj je dosti iskanje. 

Iskanje se trenutno izvaja kot linearno iskanje. Vendar pa lahko narediš veliko bolje kot to. Linearni iskanje se izvaja v O n Čas, ki je zelo počasi, čeprav lahko poiščete katero koli seznam, ki ga ima. Vaša naloga je, da se izvaja binarno iskanje, ki je teči čas O log n. To je zelo hitro. 

Ampak tam je določilo. Binarno iskanje lahko iščete le skozi predhodno razvrščena-seznamov. Zakaj je tako? No, pa si poglejmo primer. Glede na niz vrednot, senu, bomo morali iskati iglo, in v tem Na primer, celo število 3. 

Tako, da binarno iskanje deluje, je, da primerjamo srednjo vrednost matrika z iglo, podobno kot kako smo odprli telefonski imenik na sredino Stran v tednu 0. Torej po primerjavi srednji vrednosti igle, lahko zavržemo bodisi levo ali desno polovico matrike s poostritvijo svoje meje. V tem primeru, ker 3, naš igle, je manj kot 10, srednja vrednost, Pravica vezan, lahko zmanjša. 

Ampak poskusiti, da bi svoje meje tako strogo, kot je mogoče. Če je srednja vrednost ni igla, potem veste, da vam ni treba, da jo vključite v vaše iskanje. Tako da lahko vaša pravica vezana zategnite išči meje le majhen košček več, in tako naprej in tako naprej, dokler ste našli iglo. 

Torej, kaj psevdo koda izgledati? No, medtem ko še vedno iščemo preko seznam in še vedno elemente, ki so videti v, vzamemo sredino seznama in primerjajte srednja vrednost za naše iglo. Če so enaki, potem to pomeni, da ste našel iglo, in bomo lahko vrne true. 

V nasprotnem primeru, če je igla manj kot srednja vrednost, potem to pomeni, da lahko zavržemo desno polovico in samo iskanje po levi strani matrike. V nasprotnem primeru bomo iskanje desni strani polja. In na koncu, če ne boste imeli več elementov pustili za iskanje pa vam niso našli svojo iglo še ni, potem vrne false. Ker igla definitivno ni v senu. 

Zdaj, eno lepo stvar o tem psevdo koda v binarni iskanja je, da lahko razlagati tako, da bodisi ponavljajoč ali rekurzivna izvajanje. Tako da bi bilo rekurzivni, če se imenuje Iskalna funkcija v iskanju deluje na obeh polovici matrike. Pokrili bomo rekurzije malo kasneje v teku. Ampak vem, da je možnost Če želite poskusiti.