1
00:00:00,000 --> 00:00:09,560

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA Chan: Pirmā lieta, jūs varētu
Paziņojums par atradumu ir tas, ka mēs jau

3
00:00:13,120 --> 00:00:14,520
ir kods rakstīts par mums.

4
00:00:14,520 --> 00:00:16,219
To sauc par sadales kodu.

5
00:00:16,219 --> 00:00:19,060
Tāpēc mēs esam ne tikai rakstot mūsu pašu
kodu no nulles vairs.

6
00:00:19,060 --> 00:00:23,870
Drīzāk, mēs esam aizpildot tukšumu
dažās iepriekš esošo kodu.

7
00:00:23,870 --> 00:00:28,860
>> Find.c Programma piedāvā numurus
aizpildīt siena kaudzē, meklē

8
00:00:28,860 --> 00:00:33,260
siena kaudzē lietošanas iesniegts adatu,
un tas tiek panākts, aicinot veida un

9
00:00:33,260 --> 00:00:36,660
meklēt, definēti funkcijas
in helpers.c.

10
00:00:36,660 --> 00:00:38,740
Tāpēc find.c jau ir uzrakstīts.

11
00:00:38,740 --> 00:00:41,840
Tavs uzdevums ir rakstīt palīgi.

12
00:00:41,840 --> 00:00:42,940
>> Tātad, ko mēs darām?

13
00:00:42,940 --> 00:00:45,270
Mēs īsteno divas funkcijas.

14
00:00:45,270 --> 00:00:50,110
Meklēšana, kas atgriež true, ja vērtība
ir atrodams siena kaudzē, atgriežoties

15
00:00:50,110 --> 00:00:52,430
false, ja vērtība ir
ne siena kaudzē.

16
00:00:52,430 --> 00:00:59,060
Un tad mēs esam arī īstenošanas veida,
kas sakārto masīva sauc vērtības.

17
00:00:59,060 --> 00:01:01,120
Tā ļauj risināt meklēšanu.

18
00:01:01,120 --> 00:01:04,550
>> Meklēšana patlaban tiek īstenots
kā lineāru meklēšanu.

19
00:01:04,550 --> 00:01:06,620
Bet jūs varat darīt daudz labāk nekā to.

20
00:01:06,620 --> 00:01:11,610
Linear meklēšana tiek īstenota O n
laiks, kas ir diezgan lēns, lai gan tas

21
00:01:11,610 --> 00:01:14,920
var meklēt jebkuru sarakstu, ko tai.

22
00:01:14,920 --> 00:01:21,190
Tavs uzdevums ir īstenot bināro meklēšanu,
kura darbības laiks O log n.

23
00:01:21,190 --> 00:01:22,200
Tas ir diezgan ātri.

24
00:01:22,200 --> 00:01:24,240
>> Bet tur ir noteikums.

25
00:01:24,240 --> 00:01:28,910
Bināro meklēšanu var tikai meklēt
izmantojot iepriekš sakārtoti sarakstos.

26
00:01:28,910 --> 00:01:31,450
Kāpēc tā?

27
00:01:31,450 --> 00:01:33,690
Nu, aplūkosim piemēru.

28
00:01:33,690 --> 00:01:37,350
Ņemot vērā masīvs vērtībām, siena kaudzē,
Mēs ejam, lai meklē

29
00:01:37,350 --> 00:01:41,510
adatu, un šajā
Piemēram, skaitlis 3.

30
00:01:41,510 --> 00:01:45,220
>> Veidā, ka bināro meklēšanas darbiem ir tas, ka
Salīdzinot vidējo vērtību

31
00:01:45,220 --> 00:01:49,430
masīvs uz adatas, līdzīgi kā
mēs atvērām telefona grāmatu vidū

32
00:01:49,430 --> 00:01:51,720
lapa nedēļā 0.

33
00:01:51,720 --> 00:01:55,710
Tātad, pēc tam, salīdzinot vidējo vērtību
adatu, jūs varat izmest vai nu

34
00:01:55,710 --> 00:01:59,620
pa kreisi vai pa labi puse no masīva
, pievelkot savas robežas.

35
00:01:59,620 --> 00:02:04,450
Šajā gadījumā, jo 3, mūsu adata, ir
mazāk nekā 10, vidū vērtību,

36
00:02:04,450 --> 00:02:07,060
tiesības robežu var samazināt.

37
00:02:07,060 --> 00:02:09,470
>> Bet mēģināt padarīt jūsu robežas
cik stingri vien iespējams.

38
00:02:09,470 --> 00:02:12,690
Ja vidū vērtība nav adatu,
tad jūs zināt, ka jums nav nepieciešams

39
00:02:12,690 --> 00:02:14,070
iekļaut to meklēšanu.

40
00:02:14,070 --> 00:02:18,390
Tātad jūsu tiesības saistošs, var pievilkt
meklēšanas robežas tikai niecīga mazliet vairāk,

41
00:02:18,390 --> 00:02:22,840
un tā tālāk, un tā tālāk, līdz
jums atrast savu adatu.

42
00:02:22,840 --> 00:02:24,580
>> Tātad, ko tas pseido
kods izskatās?

43
00:02:24,580 --> 00:02:28,980
Nu, bet mēs joprojām meklējam cauri
sarakstu un joprojām ir

44
00:02:28,980 --> 00:02:33,540
elementi, izskatās, mēs vidū
saraksta un salīdzināt, ka

45
00:02:33,540 --> 00:02:36,020
vidējā vērtība mūsu adatu.

46
00:02:36,020 --> 00:02:38,380
Ja viņi ir vienāds, tad tas nozīmē, ka mēs esam
atrada adatu, un mēs varam

47
00:02:38,380 --> 00:02:40,160
atgriezties true.

48
00:02:40,160 --> 00:02:43,940
>> Pretējā gadījumā, ja adata ir mazāks nekā
vidējā vērtība, tad tas nozīmē, ka mēs

49
00:02:43,940 --> 00:02:48,350
var izmest pareizo pusi, un tikai
meklēt kreisajā pusē masīvs.

50
00:02:48,350 --> 00:02:51,860
Pretējā gadījumā mēs meklētu
labajā pusē masīva.

51
00:02:51,860 --> 00:02:55,470
Un beigās, ja jums nav nekādu
vairāki elementi, pa kreisi, lai meklētu, bet jūs

52
00:02:55,470 --> 00:02:58,030
nav atraduši savu adatu vēl,
tad jums atgriezties viltus.

53
00:02:58,030 --> 00:03:02,960
Jo adata noteikti
neatrodas kaudzē.

54
00:03:02,960 --> 00:03:06,200
>> Tagad viens veikls lieta par šo pseido
kods binārā meklēšana ir tas, ka tā var

55
00:03:06,200 --> 00:03:11,000
jāinterpretē kā nu iteratīvs
vai rekursīvs īstenošanu.

56
00:03:11,000 --> 00:03:14,900
Tātad tas būtu rekursīvs ja jūs sauc
meklēšanas funkcija meklēšanu

57
00:03:14,900 --> 00:03:18,400
darbojas uz abām pusēm no masīva.

58
00:03:18,400 --> 00:03:20,750
Mēs segtu rekursijas mazliet
vēlāk laikā.

59
00:03:20,750 --> 00:03:23,210
Bet zinu, ka tā ir iespēja
Ja vēlaties izmēģināt.

60
00:03:23,210 --> 00:03:24,460