ZAMYLA Chan: Pirmā lieta, jūs varētu Paziņojums par atradumu ir tas, ka mēs jau ir kods rakstīts par mums. To sauc par sadales kodu. Tāpēc mēs esam ne tikai rakstot mūsu pašu kodu no nulles vairs. Drīzāk, mēs esam aizpildot tukšumu dažās iepriekš esošo kodu. 

Find.c Programma piedāvā numurus aizpildīt siena kaudzē, meklē siena kaudzē lietošanas iesniegts adatu, un tas tiek panākts, aicinot veida un meklēt, definēti funkcijas in helpers.c. Tāpēc find.c jau ir uzrakstīts. Tavs uzdevums ir rakstīt palīgi. 

Tātad, ko mēs darām? Mēs īsteno divas funkcijas. Meklēšana, kas atgriež true, ja vērtība ir atrodams siena kaudzē, atgriežoties false, ja vērtība ir ne siena kaudzē. Un tad mēs esam arī īstenošanas veida, kas sakārto masīva sauc vērtības. Tā ļauj risināt meklēšanu. 

Meklēšana patlaban tiek īstenots kā lineāru meklēšanu. Bet jūs varat darīt daudz labāk nekā to. Linear meklēšana tiek īstenota O n laiks, kas ir diezgan lēns, lai gan tas var meklēt jebkuru sarakstu, ko tai. Tavs uzdevums ir īstenot bināro meklēšanu, kura darbības laiks O log n. Tas ir diezgan ātri. 

Bet tur ir noteikums. Bināro meklēšanu var tikai meklēt izmantojot iepriekš sakārtoti sarakstos. Kāpēc tā? Nu, aplūkosim piemēru. Ņemot vērā masīvs vērtībām, siena kaudzē, Mēs ejam, lai meklē adatu, un šajā Piemēram, skaitlis 3. 

Veidā, ka bināro meklēšanas darbiem ir tas, ka Salīdzinot vidējo vērtību masīvs uz adatas, līdzīgi kā mēs atvērām telefona grāmatu vidū lapa nedēļā 0. Tātad, pēc tam, salīdzinot vidējo vērtību adatu, jūs varat izmest vai nu pa kreisi vai pa labi puse no masīva , pievelkot savas robežas. Šajā gadījumā, jo 3, mūsu adata, ir mazāk nekā 10, vidū vērtību, tiesības robežu var samazināt. 

Bet mēģināt padarīt jūsu robežas cik stingri vien iespējams. Ja vidū vērtība nav adatu, tad jūs zināt, ka jums nav nepieciešams iekļaut to meklēšanu. Tātad jūsu tiesības saistošs, var pievilkt meklēšanas robežas tikai niecīga mazliet vairāk, un tā tālāk, un tā tālāk, līdz jums atrast savu adatu. 

Tātad, ko tas pseido kods izskatās? Nu, bet mēs joprojām meklējam cauri sarakstu un joprojām ir elementi, izskatās, mēs vidū saraksta un salīdzināt, ka vidējā vērtība mūsu adatu. Ja viņi ir vienāds, tad tas nozīmē, ka mēs esam atrada adatu, un mēs varam atgriezties true. 

Pretējā gadījumā, ja adata ir mazāks nekā vidējā vērtība, tad tas nozīmē, ka mēs var izmest pareizo pusi, un tikai meklēt kreisajā pusē masīvs. Pretējā gadījumā mēs meklētu labajā pusē masīva. Un beigās, ja jums nav nekādu vairāki elementi, pa kreisi, lai meklētu, bet jūs nav atraduši savu adatu vēl, tad jums atgriezties viltus. Jo adata noteikti neatrodas kaudzē. 

Tagad viens veikls lieta par šo pseido kods binārā meklēšana ir tas, ka tā var jāinterpretē kā nu iteratīvs vai rekursīvs īstenošanu. Tātad tas būtu rekursīvs ja jūs sauc meklēšanas funkcija meklēšanu darbojas uz abām pusēm no masīva. Mēs segtu rekursijas mazliet vēlāk laikā. Bet zinu, ka tā ir iespēja Ja vēlaties izmēģināt.