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

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA Chan: Esimene asi, mida võiks
teadet leid on see, et meil on juba

3
00:00:13,120 --> 00:00:14,520
on kood kirjutatud meile.

4
00:00:14,520 --> 00:00:16,219
Seda nimetatakse jaotus koodi.

5
00:00:16,219 --> 00:00:19,060
Nii et me ei ole ainult kirjalikult oma
koodi nullist enam.

6
00:00:19,060 --> 00:00:23,870
Pigem me täidame tühjad
mõnes olemasoleva koodi.

7
00:00:23,870 --> 00:00:28,860
>> Find.c programm küsib numbrid
täita heinakuhjas, otsib

8
00:00:28,860 --> 00:00:33,260
heinakuhjas kasutajale esitatud nõel,
ja ta teeb seda, kutsudes sorteerida ning

9
00:00:33,260 --> 00:00:36,660
Otsingu funktsioonid määratletud
aastal helpers.c.

10
00:00:36,660 --> 00:00:38,740
Nii find.c on kirjutatud juba.

11
00:00:38,740 --> 00:00:41,840
Sinu ülesanne on kirjutada abilised.

12
00:00:41,840 --> 00:00:42,940
>> Niisiis, mida me teeme?

13
00:00:42,940 --> 00:00:45,270
Me rakendamisel kaks ülesannet.

14
00:00:45,270 --> 00:00:50,110
Search, mis tagastab tõene kui väärtus
leitakse heinakuhjas, tagasi

15
00:00:50,110 --> 00:00:52,430
false, kui väärtus on
ei heinakuhjas.

16
00:00:52,430 --> 00:00:59,060
Ja siis me ka rakendatakse sort,
mis sordib massiivi nimetatakse väärtused.

17
00:00:59,060 --> 00:01:01,120
Teeme tegeleda otsing.

18
00:01:01,120 --> 00:01:04,550
>> Otsi praegu rakendatakse
lineaarse otsing.

19
00:01:04,550 --> 00:01:06,620
Aga sa saad teha palju paremini.

20
00:01:06,620 --> 00:01:11,610
Linear otsing rakendatakse O n
aega, mis on üsna aeglane, kuigi see

21
00:01:11,610 --> 00:01:14,920
saate otsida iga nimekirja talle antud.

22
00:01:14,920 --> 00:01:21,190
Sinu ülesanne on viia ellu binaarne otsing,
mis on otsa aeg O log n.

23
00:01:21,190 --> 00:01:22,200
See on päris kiire.

24
00:01:22,200 --> 00:01:24,240
>> Aga seal on klausel.

25
00:01:24,240 --> 00:01:28,910
Binary otsing vaid otsida
läbi eelnevalt sorteeritud nimekirja.

26
00:01:28,910 --> 00:01:31,450
Miks see nii on?

27
00:01:31,450 --> 00:01:33,690
Noh, vaatame näiteks.

28
00:01:33,690 --> 00:01:37,350
Kuna massiivi väärtusi, heinakuhjas,
me otsima

29
00:01:37,350 --> 00:01:41,510
võtta nõel ja selles
Näiteks täisarv 3.

30
00:01:41,510 --> 00:01:45,220
>> Nii, et binaarne otsing toimib on see,
me võrdleme keskel väärtus

31
00:01:45,220 --> 00:01:49,430
massiivi nõela meelega kuidas
avasime telefoniraamatust keskel

32
00:01:49,430 --> 00:01:51,720
lehekülje Week 0.

33
00:01:51,720 --> 00:01:55,710
Nii et pärast võrreldes keskmise väärtuse
nõel, võite visata kas

34
00:01:55,710 --> 00:01:59,620
vasakule või paremale poole massiivi
pingutades oma piire.

35
00:01:59,620 --> 00:02:04,450
Sel juhul, kuna 3, meie nõel on
vähem kui 10, keskmine väärtus,

36
00:02:04,450 --> 00:02:07,060
seonduv õigus võib väheneda.

37
00:02:07,060 --> 00:02:09,470
>> Aga proovi teha oma piire
nii range kui võimalik.

38
00:02:09,470 --> 00:02:12,690
Kui keset väärtus ei ole nõela
siis sa tead, et sa ei pea

39
00:02:12,690 --> 00:02:14,070
lisada selle oma otsingut.

40
00:02:14,070 --> 00:02:18,390
Nii et sa oled kindlasti ei pinguta
otsi piire natukene rohkem,

41
00:02:18,390 --> 00:02:22,840
ja nii edasi ja nii edasi, kuni
leiad nõela.

42
00:02:22,840 --> 00:02:24,580
>> Mis siis pseudo
kood välja näeb?

43
00:02:24,580 --> 00:02:28,980
Noh, kui me otsime veel läbi
nimekirja ja veel

44
00:02:28,980 --> 00:02:33,540
elemente, et uurida, võtame keskel
nimekirja ja võrrelda seda

45
00:02:33,540 --> 00:02:36,020
keskel väärtust meie nõel.

46
00:02:36,020 --> 00:02:38,380
Kui nad võrdsed, siis see tähendab, et me oleme
leidsin nõela, ja me saame

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

48
00:02:40,160 --> 00:02:43,940
>> Vastasel juhul, kui nõel on alla
keskel väärtus, siis see tähendab, et me

49
00:02:43,940 --> 00:02:48,350
ära visata paremal poolel ja lihtsalt
search vasakul massiiv.

50
00:02:48,350 --> 00:02:51,860
Vastasel juhul me kontrollime
paremal pool massiivi.

51
00:02:51,860 --> 00:02:55,470
Ja lõpuks, kui sa ei ole üldse
rohkem elemente vasakule otsida aga sa

52
00:02:55,470 --> 00:02:58,030
ei ole leidnud oma nõela veel
siis tagastab false.

53
00:02:58,030 --> 00:03:02,960
Kuna nõel kindlasti
ei heinakuhjas.

54
00:03:02,960 --> 00:03:06,200
>> Nüüd üks kena asi see pseudo
koodi binaarne otsing on see, et see ei

55
00:03:06,200 --> 00:03:11,000
võib tõlgendada kas iteratiivne
või rekursiivne rakendamine.

56
00:03:11,000 --> 00:03:14,900
Seega oleks rekursiivne kui sa helistasid
otsingu funktsiooni otsing

57
00:03:14,900 --> 00:03:18,400
toimida kas pooles massiivi.

58
00:03:18,400 --> 00:03:20,750
Me katame rekursioon natuke
hiljem muidugi.

59
00:03:20,750 --> 00:03:23,210
Aga tean, et see on võimalus
Kui soovite, et proovida.

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