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

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA Чан: Першае, што вы маглі б
апавяшчэнне аб знаходцы з'яўляецца тое, што мы ўжо

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
Пошук, які вяртае ісціну, калі значэнне
знаходзіцца ў стозе сена, вяртаючыся

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
Лінейны пошук ажыццяўляецца ў O п
час, якое з'яўляецца даволі павольным, хоць гэта

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
Двайковага пошуку можна толькі пошук
праз папярэдне парадку п. спісаў.

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
У гэтым выпадку, паколькі 3, наша іголка, з'яўляецца
менш за 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