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

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA CHAN: Die eerste ding wat jy dalk
kennisgewing oor vonds is dat ons reeds

3
00:00:13,120 --> 00:00:14,520
het 'n kode geskryf vir ons.

4
00:00:14,520 --> 00:00:16,219
Dit is die verspreiding kode genoem.

5
00:00:16,219 --> 00:00:19,060
So ons is nie net die skryf van ons eie
kode van nuuts af nie.

6
00:00:19,060 --> 00:00:23,870
Inteendeel, is ons in te vul die leemtes
in 'n paar pre-bestaande kode.

7
00:00:23,870 --> 00:00:28,860
>> Die find.c program vra vir nommers
die hooiberg te vul, soek die

8
00:00:28,860 --> 00:00:33,260
hooiberg vir 'n gebruiker voorgelê naald,
en doen dit deur te bel soort en

9
00:00:33,260 --> 00:00:36,660
Soek, funksies gedefinieer
in helpers.c.

10
00:00:36,660 --> 00:00:38,740
So find.c is reeds geskryf.

11
00:00:38,740 --> 00:00:41,840
Jou werk is om helpers te skryf.

12
00:00:41,840 --> 00:00:42,940
>> So, wat doen ons?

13
00:00:42,940 --> 00:00:45,270
Ons is die uitvoering van twee funksies.

14
00:00:45,270 --> 00:00:50,110
Soek, wat terugkeer waar as 'n waarde
word gevind in die hooiberg, terugkeer

15
00:00:50,110 --> 00:00:52,430
valse indien die waarde is
nie in die hooiberg.

16
00:00:52,430 --> 00:00:59,060
En dan is ons ook die implementering van aard,
wat allerhande die skikking met die naam waardes.

17
00:00:59,060 --> 00:01:01,120
So laat se pak soek.

18
00:01:01,120 --> 00:01:04,550
>> Soek tans geïmplementeer
as 'n lineêre soek.

19
00:01:04,550 --> 00:01:06,620
Maar jy kan nie veel beter as dit.

20
00:01:06,620 --> 00:01:11,610
Lineêre soektog in O N geïmplementeer
tyd, wat baie stadig, maar dit

21
00:01:11,610 --> 00:01:14,920
kan soek enige gegewe lys om dit te.

22
00:01:14,920 --> 00:01:21,190
Jou werk is om binêre soek om te implementeer,
wat loop tyd O log n.

23
00:01:21,190 --> 00:01:22,200
Dit is redelik vinnig.

24
00:01:22,200 --> 00:01:24,240
>> Maar daar is 'n bepaling.

25
00:01:24,240 --> 00:01:28,910
Binêre soek kan net soek
deur pre-gesorteer lyste.

26
00:01:28,910 --> 00:01:31,450
Hoekom is dit?

27
00:01:31,450 --> 00:01:33,690
Wel, laat ons kyk na 'n voorbeeld.

28
00:01:33,690 --> 00:01:37,350
Gegewe 'n verskeidenheid van waardes, die hooiberg,
ons gaan om te kyk

29
00:01:37,350 --> 00:01:41,510
vir 'n naald, en in hierdie
Byvoorbeeld, die heelgetal 3.

30
00:01:41,510 --> 00:01:45,220
>> Die manier waarop binêre soek werk, is dat
ons die middelste waarde van vergelyk

31
00:01:45,220 --> 00:01:49,430
die skikking aan die naald, baie soos hoe
Ons maak 'n telefoon boek na die middel

32
00:01:49,430 --> 00:01:51,720
bladsy in Week 0.

33
00:01:51,720 --> 00:01:55,710
So na die middelste waarde te vergelyk
die naald, kan jy weggooi óf die

34
00:01:55,710 --> 00:01:59,620
linker-of die regter helfte van die skikking
deur strenger jou perke.

35
00:01:59,620 --> 00:02:04,450
In hierdie geval, sedert 3, ons naald, is
minder as 10, die middelste waarde, die

36
00:02:04,450 --> 00:02:07,060
reg gebind kan verminder.

37
00:02:07,060 --> 00:02:09,470
>> Maar probeer om jou grense te maak
so styf as moontlik.

38
00:02:09,470 --> 00:02:12,690
As die middelste waarde is nie die naald,
dan moet jy weet dat jy nie nodig het om te

39
00:02:12,690 --> 00:02:14,070
sluit dit in jou soektog.

40
00:02:14,070 --> 00:02:18,390
So jou reg gebind kan draai die
Soek perke net 'n klein bietjie meer,

41
00:02:18,390 --> 00:02:22,840
en so aan en so voort, totdat
jy jou naald.

42
00:02:22,840 --> 00:02:24,580
>> So, wat nie die pseudo
kode lyk?

43
00:02:24,580 --> 00:02:28,980
Wel, terwyl ons nog steeds deur
die lys en nog

44
00:02:28,980 --> 00:02:33,540
elemente om te kyk in, neem ons die middel
van die lys en vergelyk dit

45
00:02:33,540 --> 00:02:36,020
Midde-waarde aan ons naald.

46
00:02:36,020 --> 00:02:38,380
As hulle gelyk is, dan beteken dit dat ons het
het gevind dat die naald, en ons kan

47
00:02:38,380 --> 00:02:40,160
terug waar.

48
00:02:40,160 --> 00:02:43,940
>> Andersins, as die naald is minder as
Die middelste waarde is, dan beteken dit dat ons

49
00:02:43,940 --> 00:02:48,350
kan die regter helfte weggooi en net
soek die linkerkant van die skikking.

50
00:02:48,350 --> 00:02:51,860
Andersins, sal ons soek die
regterkant van die skikking.

51
00:02:51,860 --> 00:02:55,470
En aan die einde, as jy het nie
meer elemente links te soek, maar jy

52
00:02:55,470 --> 00:02:58,030
nog nie jou naald gevind nie,
dan moet jy terugkeer, vals is.

53
00:02:58,030 --> 00:03:02,960
Omdat die naald beslis
is nie in die hooiberg.

54
00:03:02,960 --> 00:03:06,200
>> Nou, 'n netjiese ding oor hierdie pseudo
kode in binêre soek is, is dat dit kan

55
00:03:06,200 --> 00:03:11,000
geïnterpreteer word as óf 'n iteratiewe
of rekursiewe implementering.

56
00:03:11,000 --> 00:03:14,900
So is dit rekursiewe sou wees as jy genoem
die soek funksie binne die soektog

57
00:03:14,900 --> 00:03:18,400
funksioneer op óf die helfte van die skikking.

58
00:03:18,400 --> 00:03:20,750
Ons sal dek rekursie 'n bietjie
later in die kursus.

59
00:03:20,750 --> 00:03:23,210
Maar weet dat dit is 'n opsie
As jy wil om te probeer.

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