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

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA CHAN: Den første ting du måske
bekendtgørelse om fund er, at vi allerede

3
00:00:13,120 --> 00:00:14,520
have kode skrevet til os.

4
00:00:14,520 --> 00:00:16,219
Dette kaldes fordeling kode.

5
00:00:16,219 --> 00:00:19,060
Så vi ikke bare skrive vores egen
kode fra bunden længere.

6
00:00:19,060 --> 00:00:23,870
Snarere, vi udfylder hulrum
i nogle eksisterende kode.

7
00:00:23,870 --> 00:00:28,860
>> Det find.c programmet beder for tal
at fylde høstak, søger

8
00:00:28,860 --> 00:00:33,260
høstak for en bruger indsendte nål,
og det gør dette ved at kalde sortere og

9
00:00:33,260 --> 00:00:36,660
søgning, funktioner defineret
i helpers.c.

10
00:00:36,660 --> 00:00:38,740
Så find.c er skrevet allerede.

11
00:00:38,740 --> 00:00:41,840
Dit job er at skrive hjælpere.

12
00:00:41,840 --> 00:00:42,940
>> Så hvad gør vi?

13
00:00:42,940 --> 00:00:45,270
Vi gennemføre to funktioner.

14
00:00:45,270 --> 00:00:50,110
Søg, som returnerer true, hvis en værdi
er fundet i høstakken, vender tilbage

15
00:00:50,110 --> 00:00:52,430
falsk, hvis værdien er
ikke i høstakken.

16
00:00:52,430 --> 00:00:59,060
Og så er vi også gennemføre slags,
som sorterer array kaldet værdier.

17
00:00:59,060 --> 00:01:01,120
Så lad os tage fat søgning.

18
00:01:01,120 --> 00:01:04,550
>> Søg i øjeblikket gennemføres
som en lineær søgning.

19
00:01:04,550 --> 00:01:06,620
Men du kan gøre meget bedre end det.

20
00:01:06,620 --> 00:01:11,610
Lineær søgning er implementeret i O n
tid, hvilket er ret langsomt, selv om den

21
00:01:11,610 --> 00:01:14,920
kan søge enhver liste, det fik.

22
00:01:14,920 --> 00:01:21,190
Dit job er at implementere binær søgning,
der har kørt tid O af log n.

23
00:01:21,190 --> 00:01:22,200
Det er temmelig hurtigt.

24
00:01:22,200 --> 00:01:24,240
>> Men der er en bestemmelse.

25
00:01:24,240 --> 00:01:28,910
Binær søgning kan kun søge
gennem pre-sorterede lister.

26
00:01:28,910 --> 00:01:31,450
Hvorfor er det?

27
00:01:31,450 --> 00:01:33,690
Nå, lad os se på et eksempel.

28
00:01:33,690 --> 00:01:37,350
I betragtning af en matrix af værdier, høstak,
vi kommer til at være på udkig

29
00:01:37,350 --> 00:01:41,510
efter en nål, og i denne
eksempel heltal 3.

30
00:01:41,510 --> 00:01:45,220
>> Den måde, at binær søgning værker er, at
Sammenligner vi den midterste værdi af

31
00:01:45,220 --> 00:01:49,430
array til nålen, meget gerne, hvordan
vi åbnede en telefonbog til midten

32
00:01:49,430 --> 00:01:51,720
side i uge 0.

33
00:01:51,720 --> 00:01:55,710
Så efter sammenligning af den midterste værdi til
nålen, kan du kassere enten

34
00:01:55,710 --> 00:01:59,620
venstre eller højre halvdel af array
ved at stramme dine grænser.

35
00:01:59,620 --> 00:02:04,450
I dette tilfælde, idet 3 vores nål, er
mindre end 10, den midterste værdi,

36
00:02:04,450 --> 00:02:07,060
højre bundet kan falde.

37
00:02:07,060 --> 00:02:09,470
>> Men prøv at gøre dine grænser
så stramt som muligt.

38
00:02:09,470 --> 00:02:12,690
Hvis den midterste værdi ikke er den nål,
så ved du at du ikke behøver at

39
00:02:12,690 --> 00:02:14,070
medtage den i din søgning.

40
00:02:14,070 --> 00:02:18,390
Så din højre grænse kan stramme den
søgning bounds bare en lille smule mere,

41
00:02:18,390 --> 00:02:22,840
og så videre og så videre, indtil
du finder din nål.

42
00:02:22,840 --> 00:02:24,580
>> Så hvad gør pseudo
kode se ud?

43
00:02:24,580 --> 00:02:28,980
Nå, mens vi leder stadig igennem
listen og stadig have

44
00:02:28,980 --> 00:02:33,540
elementer til at se på, tager vi den midterste
af listen, og sammenligne det

45
00:02:33,540 --> 00:02:36,020
midterste værdi til vores nål.

46
00:02:36,020 --> 00:02:38,380
Hvis de er lige, så det betyder, at vi har
fundet nålen, og vi kan

47
00:02:38,380 --> 00:02:40,160
returnere sandt.

48
00:02:40,160 --> 00:02:43,940
>> Ellers, hvis nålen er mindre end
den midterste værdi, så det betyder, at vi

49
00:02:43,940 --> 00:02:48,350
kan skille den højre halvdel og bare
søge i venstre side af matrixen.

50
00:02:48,350 --> 00:02:51,860
Ellers vil vi søge
højre side af matrixen.

51
00:02:51,860 --> 00:02:55,470
Og til sidst, hvis du ikke har nogen
flere elementer tilbage til søgning, men du

52
00:02:55,470 --> 00:02:58,030
har ikke fundet nålen endnu,
så du vender tilbage falsk.

53
00:02:58,030 --> 00:03:02,960
Da nålen helt
er ikke i høstakken.

54
00:03:02,960 --> 00:03:06,200
>> Nu, en pæn ting om denne pseudo
kode i binær søgning er, at det kan

55
00:03:06,200 --> 00:03:11,000
tolkes som enten en iterativ
eller rekursive gennemførelse.

56
00:03:11,000 --> 00:03:14,900
Så det ville være rekursiv hvis du kaldte
søgefunktionen i søgningen

57
00:03:14,900 --> 00:03:18,400
kan fungere på hver halvdel af matrixen.

58
00:03:18,400 --> 00:03:20,750
Vi dækker rekursion lidt
senere i kurset.

59
00:03:20,750 --> 00:03:23,210
Men ved, at det er en mulighed
hvis du gerne vil prøve.

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