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

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA CHAN: Het eerste wat je zou
bericht over vondst is dat we al

3
00:00:13,120 --> 00:00:14,520
hebben code geschreven voor ons.

4
00:00:14,520 --> 00:00:16,219
Dit heet verdeelsleutel.

5
00:00:16,219 --> 00:00:19,060
Zodat we niet alleen het schrijven van onze eigen
coderen van kras meer.

6
00:00:19,060 --> 00:00:23,870
Integendeel, we vullen de holtes
in sommige reeds bestaande code.

7
00:00:23,870 --> 00:00:28,860
>> De status van huidige map programma vraagt ​​voor getallen
om de hooiberg te vullen, zoekt het

8
00:00:28,860 --> 00:00:33,260
hooiberg voor een gebruiker ingediend naald,
en doet dit door te bellen naar soort en

9
00:00:33,260 --> 00:00:36,660
zoeken, functies gedefinieerd
in helpers.c.

10
00:00:36,660 --> 00:00:38,740
Dus status van huidige map is al geschreven.

11
00:00:38,740 --> 00:00:41,840
Jouw taak is om helpers te schrijven.

12
00:00:41,840 --> 00:00:42,940
>> Dus wat doen we?

13
00:00:42,940 --> 00:00:45,270
We implementeren twee functies.

14
00:00:45,270 --> 00:00:50,110
Zoek geeft true als een waarde
is te vinden in de hooiberg, terugkerende

15
00:00:50,110 --> 00:00:52,430
false als de waarde is
niet in de hooiberg.

16
00:00:52,430 --> 00:00:59,060
En dan zijn we ook de uitvoering van soort,
die sorteert de array genoemd waarden.

17
00:00:59,060 --> 00:01:01,120
Dus laten we zoeken te pakken.

18
00:01:01,120 --> 00:01:04,550
>> Zoeken wordt momenteel geïmplementeerd
als een lineair zoeken.

19
00:01:04,550 --> 00:01:06,620
Maar je kunt veel beter dan dat.

20
00:01:06,620 --> 00:01:11,610
Lineair zoeken is in O n geïmplementeerd
tijd, die is vrij langzaam, hoewel

21
00:01:11,610 --> 00:01:14,920
kan naar elke lijst gegeven.

22
00:01:14,920 --> 00:01:21,190
Jouw taak is om binary search uit te voeren,
die tijd O van log n heeft gelopen.

23
00:01:21,190 --> 00:01:22,200
Dat is behoorlijk snel.

24
00:01:22,200 --> 00:01:24,240
>> Maar er is een bepaling.

25
00:01:24,240 --> 00:01:28,910
Binary search kunt alleen zoeken
door voorgesorteerd lijsten.

26
00:01:28,910 --> 00:01:31,450
Waarom is dat?

27
00:01:31,450 --> 00:01:33,690
Nou, laten we eens kijken naar een voorbeeld.

28
00:01:33,690 --> 00:01:37,350
Gegeven een matrix met waarden, de hooiberg,
we gaan op zoek

29
00:01:37,350 --> 00:01:41,510
een naald, en in dit
Bijvoorbeeld, het gehele getal 3.

30
00:01:41,510 --> 00:01:45,220
>> De manier waarop binary search werkt is dat
Vergelijken we de middelste waarde van

31
00:01:45,220 --> 00:01:49,430
de array om de naald, net als hoe
we een telefoonboek geopend voor het midden

32
00:01:49,430 --> 00:01:51,720
pagina in week 0.

33
00:01:51,720 --> 00:01:55,710
Dus na de middelste waarde te vergelijken met
de naald, kunt u weggooien ofwel de

34
00:01:55,710 --> 00:01:59,620
linker of de rechter helft van de array
door aanscherping van je grenzen.

35
00:01:59,620 --> 00:02:04,450
In dit geval, aangezien 3 Onze naald is
minder dan 10, de middelste waarde, de

36
00:02:04,450 --> 00:02:07,060
recht gebonden kan verminderen.

37
00:02:07,060 --> 00:02:09,470
>> Maar probeer je grenzen te maken
zo strak mogelijk.

38
00:02:09,470 --> 00:02:12,690
Als de middelste waarde is niet de naald,
dan weet je dat je niet hoeft te

39
00:02:12,690 --> 00:02:14,070
opnemen in uw zoekopdracht.

40
00:02:14,070 --> 00:02:18,390
Dus je rechter gebonden kan draai de
zoeken grenzen slechts een klein beetje meer,

41
00:02:18,390 --> 00:02:22,840
enzovoort enzovoort, totdat
je je naald te vinden.

42
00:02:22,840 --> 00:02:24,580
>> Dus wat doet de pseudo
code eruit?

43
00:02:24,580 --> 00:02:28,980
Nou, nu we nog altijd kijken door
de lijst en hebben nog steeds

44
00:02:28,980 --> 00:02:33,540
elementen om te kijken in, nemen we de middelste
van de lijst en dat vergelijken

45
00:02:33,540 --> 00:02:36,020
middelste waarde voor onze naald.

46
00:02:36,020 --> 00:02:38,380
Als ze gelijk zijn, dan betekent dat we hebben
vond de naald, en we kunnen

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

48
00:02:40,160 --> 00:02:43,940
>> Anders, als de naald is minder dan
de middelste waarde, dan betekent dat we

49
00:02:43,940 --> 00:02:48,350
kan de rechter helft weggooien en gewoon
zoek de linkerzijde van de array.

50
00:02:48,350 --> 00:02:51,860
Anders zullen we zoeken in de
rechterzijde van de array.

51
00:02:51,860 --> 00:02:55,470
En aan het eind, als je die niet hebt
meer elementen overgelaten om te zoeken, maar je

52
00:02:55,470 --> 00:02:58,030
nog niet gevonden je naald,
dan return false u.

53
00:02:58,030 --> 00:03:02,960
Omdat de naald zeker
is niet in de hooiberg.

54
00:03:02,960 --> 00:03:06,200
>> Nu, een keurige ding over dit pseudo
code in binary search is dat het kan

55
00:03:06,200 --> 00:03:11,000
worden geïnterpreteerd als een iteratief
of recursieve implementatie.

56
00:03:11,000 --> 00:03:14,900
Dus het zou recursieve zijn als je geroepen
de zoekfunctie binnen de zoekopdracht

57
00:03:14,900 --> 00:03:18,400
werken aan elke helft van de array.

58
00:03:18,400 --> 00:03:20,750
We zullen recursie bestrijken een beetje
later in de cursus.

59
00:03:20,750 --> 00:03:23,210
Maar weet wel dat het een optie is
als je wilt proberen.

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