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

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA CHAN: Първото нещо, което може
известие за находка е, че ние вече

3
00:00:13,120 --> 00:00:14,520
са код, написан за нас.

4
00:00:14,520 --> 00:00:16,219
Това се нарича разпределение код.

5
00:00:16,219 --> 00:00:19,060
Така че ние не сме просто писане нашата собствена
кода от нулата вече.

6
00:00:19,060 --> 00:00:23,870
Напротив, ние сме попълване на кухини
в някои предварително съществуващ код.

7
00:00:23,870 --> 00:00:28,860
>> Програмата find.c пита за номера
за запълване на купа сено, търси в

8
00:00:28,860 --> 00:00:33,260
Купа сено за потребител предостави игла,
и да го прави това, като се обадите на сортиране и

9
00:00:33,260 --> 00:00:36,660
търсене, функции, дефинирани
в helpers.c.

10
00:00:36,660 --> 00:00:38,740
Така find.c е писано вече.

11
00:00:38,740 --> 00:00:41,840
Вашата задача е да се напише помощници.

12
00:00:41,840 --> 00:00:42,940
>> И така, какво ще правим?

13
00:00:42,940 --> 00:00:45,270
Ние сме за прилагане на две функции.

14
00:00:45,270 --> 00:00:50,110
Search, която връща истина, ако стойността
се намира в купа сено, връщайки

15
00:00:50,110 --> 00:00:52,430
невярно, ако стойността е
не в купа сено.

16
00:00:52,430 --> 00:00:59,060
И след това ние сме също така прилагане на сортиране,
който сортира масива нарича стойности.

17
00:00:59,060 --> 00:01:01,120
Така че нека да се справи с търсенето.

18
00:01:01,120 --> 00:01:04,550
>> Търси се изпълнява в момента
като линейна търсене.

19
00:01:04,550 --> 00:01:06,620
Но можете да направите много по-добре от това.

20
00:01:06,620 --> 00:01:11,610
Линеен търсене се осъществява в О п
време, което е доста бавно, въпреки че

21
00:01:11,610 --> 00:01:14,920
може да търси всеки списък, дадено му.

22
00:01:14,920 --> 00:01:21,190
Вашата работа е да се приложат двоично търсене,
която тече в момента O на дневник п.

23
00:01:21,190 --> 00:01:22,200
Това е доста бързо.

24
00:01:22,200 --> 00:01:24,240
>> Но има една уговорка.

25
00:01:24,240 --> 00:01:28,910
Binary търсене може да търси само
чрез предварително сортирани списъци.

26
00:01:28,910 --> 00:01:31,450
Защо е това?

27
00:01:31,450 --> 00:01:33,690
Е, нека да разгледаме един пример.

28
00:01:33,690 --> 00:01:37,350
Предвид масив от стойности, купа сено,
ние ще трябва да се търси

29
00:01:37,350 --> 00:01:41,510
игла, и в този
Например, числото 3.

30
00:01:41,510 --> 00:01:45,220
>> Начинът, по който двоично търсене работи е, че
сравним средната стойност на

31
00:01:45,220 --> 00:01:49,430
масива до иглата, който много прилича как
ние отвори телефонния указател към средата

32
00:01:49,430 --> 00:01:51,720
страница в Седмица 0.

33
00:01:51,720 --> 00:01:55,710
Така че, след сравняване на средната стойност за
иглата, можете да отхвърлите или на

34
00:01:55,710 --> 00:01:59,620
лявата или дясната половина на масива
чрез затягане на вашите граници.

35
00:01:59,620 --> 00:02:04,450
В този случай, тъй като три, нашата игла, е
по-малко от 10, средната стойност на

36
00:02:04,450 --> 00:02:07,060
дясната граница може да се понижат.

37
00:02:07,060 --> 00:02:09,470
>> Но опитайте се да направите вашите граници
възможно най-стегнато.

38
00:02:09,470 --> 00:02:12,690
Ако средната стойност не е иглата
тогава знаете, че не е нужно да се

39
00:02:12,690 --> 00:02:14,070
го включи в търсенето си.

40
00:02:14,070 --> 00:02:18,390
Така че си прав обвързана да затегнете
търсене границите съвсем малко повече,

41
00:02:18,390 --> 00:02:22,840
и така нататък, и така нататък, докато
да намерите вашата игла.

42
00:02:22,840 --> 00:02:24,580
>> Така че това, което прави псевдо
код изглежда?

43
00:02:24,580 --> 00:02:28,980
Е, докато ние все още търсим чрез
списъка и все още имат

44
00:02:28,980 --> 00:02:33,540
елементи, за да търсите, ние приемаме средата
от списъка и сравни, че

45
00:02:33,540 --> 00:02:36,020
средната стойност за нашата игла.

46
00:02:36,020 --> 00:02:38,380
Ако те са равни, тогава това означава, че ние имаме
Намерени иглата, и ние можем да

47
00:02:38,380 --> 00:02:40,160
връщане вярно.

48
00:02:40,160 --> 00:02:43,940
>> В противен случай, ако иглата е по-малко от
средната стойност, тогава това означава, че ние

49
00:02:43,940 --> 00:02:48,350
може да се изхвърли в дясната половина и просто
търсене на лявата страна на масива.

50
00:02:48,350 --> 00:02:51,860
В противен случай, ние ще се търси в
дясната част на масива.

51
00:02:51,860 --> 00:02:55,470
И в края на краищата, ако не оказват
повече елементи оставяли да търсите, но вие

52
00:02:55,470 --> 00:02:58,030
не са намерили своя игла все още,
След това се върнете фалшива.

53
00:02:58,030 --> 00:03:02,960
Тъй като иглата определено
не е в купа сено.

54
00:03:02,960 --> 00:03:06,200
>> Сега, едно нещо, за чист този псевдо
код в двоичен търсене е, че тя може да

55
00:03:06,200 --> 00:03:11,000
да се тълкува или като един повтарящ
или рекурсивно изпълнение.

56
00:03:11,000 --> 00:03:14,900
Така че би било рекурсивно ако сте се обадили
функцията за търсене в рамките на търсенето

57
00:03:14,900 --> 00:03:18,400
функционира или половината от масива.

58
00:03:18,400 --> 00:03:20,750
Ще разгледаме рекурсия малко
по-късно в процеса.

59
00:03:20,750 --> 00:03:23,210
Но знам, че това е опция
ако искате да опитате.

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