1
00:00:00,000 --> 00:00:13,300

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Прывітанне, я Роб.

3
00:00:15,010 --> 00:00:16,790
Як мы выкарыстоўваем бінарны пошук?

4
00:00:16,790 --> 00:00:18,770
Давайце высвятлім.

5
00:00:18,770 --> 00:00:23,400
Так, звярніце ўвагу, што гэты пошук мы збіраемся
рэалізаваць рэкурсіўна.

6
00:00:23,400 --> 00:00:27,470
Акрамя таго, можна рэалізаваць бінарны пошук
шматкроць, так што калі вы гэта зрабілі,

7
00:00:27,470 --> 00:00:29,280
гэта цалкам нармальна.

8
00:00:29,280 --> 00:00:32,820
>> Цяпер спачатку, давайце памятаць, што
Параметры для пошуку прызначаныя для.

9
00:00:32,820 --> 00:00:36,120
Тут мы бачым дзесятковага значэнне, якое
павінна быць значэнне карыстальнік

10
00:00:36,120 --> 00:00:37,320
пошук.

11
00:00:37,320 --> 00:00:40,800
Мы бачым масіў Int каштоўнасці, якія
гэта масіў, у якім мы

12
00:00:40,800 --> 00:00:42,520
пошук значэння.

13
00:00:42,520 --> 00:00:45,602
І мы бачым, Int N, які з'яўляецца
даўжыня нашага масіва.

14
00:00:45,602 --> 00:00:47,410
>> Цяпер, першае, што ў першую чаргу.

15
00:00:47,410 --> 00:00:51,350
Мы правяраем, калі п роўна 0, у
гэтым выпадку мы вярнуцца ілжывым.

16
00:00:51,350 --> 00:00:54,770
Вось толькі гаварыць, калі ў нас ёсць пусты
Масіў, кошт відавочна не будзе ў

17
00:00:54,770 --> 00:00:57,860
пусты масіў, таму мы можам вярнуцца ілжывым.

18
00:00:57,860 --> 00:01:01,250
>> Зараз, мы на самай справе хочам зрабіць двайковы
Пошук частка бінарнага пошуку.

19
00:01:01,250 --> 00:01:04,780
Так, мы хочам знайсці сярэдзіну
элемент гэтага масіва.

20
00:01:04,780 --> 00:01:09,130
Тут мы гаворым сярэдняга роўная п дзеліцца
на 2, з сярэдзіны элемент

21
00:01:09,130 --> 00:01:12,240
будзе даўжыня
падзяліць на 2 наш масіў.

22
00:01:12,240 --> 00:01:15,040
Цяпер мы збіраемся, каб праверыць, калі
сярэдні элемент роўны значэння, калі мы знаходзімся

23
00:01:15,040 --> 00:01:16,160
пошук.

24
00:01:16,160 --> 00:01:21,030
Так што, калі значэнні сярэдняга роўная кошту, мы
можа вярнуцца дакладна, паколькі мы выявілі, што

25
00:01:21,030 --> 00:01:22,810
значэнне ў масіве.

26
00:01:22,810 --> 00:01:26,380
>> Але калі гэта не так, цяпер
мы павінны зрабіць рэкурсіўны

27
00:01:26,380 --> 00:01:27,840
крок бінарнага пошуку.

28
00:01:27,840 --> 00:01:30,450
Нам трэба шукаць альбо
злева ад масіва або

29
00:01:30,450 --> 00:01:32,320
сярэдні масіва.

30
00:01:32,320 --> 00:01:39,280
Дык вось, мы гаворым, калі значэння ў сярэдзіне з'яўляецца
менш, чым значэнне, што азначае, што кошт

31
00:01:39,280 --> 00:01:41,350
было больш, чым у сярэдзіне
масіва.

32
00:01:41,350 --> 00:01:45,790
Так значэнне павінна быць справа ад
элемент, які мы толькі што глядзелі.

33
00:01:45,790 --> 00:01:48,090
>> Дык вось, мы збіраемся
пошук рэкурсіўна.

34
00:01:48,090 --> 00:01:50,320
І мы будзем глядзець на тое, што мы перадаем
да гэтага ў секунду.

35
00:01:50,320 --> 00:01:53,440
Але мы збіраемся шукаць у
Права сярэдняга элемента.

36
00:01:53,440 --> 00:01:57,710
А ў іншым выпадку, гэта азначае, што
значэнне было менш, чым у сярэдзіне

37
00:01:57,710 --> 00:02:00,660
Масіў, і такім чынам мы збіраемся
шукаць налева.

38
00:02:00,660 --> 00:02:03,520
Цяпер левая будзе
крыху лягчэй глядзець.

39
00:02:03,520 --> 00:02:07,770
Такім чынам, мы бачым, што мы рэкурсіўна
выкліку пошуку, дзе першы

40
00:02:07,770 --> 00:02:10,120
аргумент, зноў жа, значэнне
мы шукаем больш.

41
00:02:10,120 --> 00:02:14,970
Другі аргумент будзе
Масіў, мы шукалі больш.

42
00:02:14,970 --> 00:02:17,090
І апошні элемент зараз з'яўляецца сярэдні.

43
00:02:17,090 --> 00:02:21,650
Памятаеце апошні параметр з'яўляецца нашым унутр
п, так што гэта даўжыня нашага масіва.

44
00:02:21,650 --> 00:02:25,310
>> У рэкурсіўнага выкліку для пошуку, мы
цяпер кажуць, што даўжыня

45
00:02:25,310 --> 00:02:27,230
масіў сярэдні.

46
00:02:27,230 --> 00:02:32,900
Так што, калі наш масіў быў памерам 20 і мы
Пошук па індэксе 10, так як сярэдзіна

47
00:02:32,900 --> 00:02:36,930
20 падзяліць на 2, што азначае, што мы
праходзячы 10 як новы

48
00:02:36,930 --> 00:02:38,300
даўжыня нашага масіва.

49
00:02:38,300 --> 00:02:41,910
Памятаеце, што калі ў вас ёсць масіў
даўжынёй 10, гэта азначае, што дзейнічае

50
00:02:41,910 --> 00:02:45,450
элементы знаходзяцца ў індэксаў ад 0 да 9.

51
00:02:45,450 --> 00:02:50,120
Так што гэта менавіта тое, што мы хочам
паказаць наш абноўлены масіў - левы

52
00:02:50,120 --> 00:02:53,010
Масіў з сярэдняга элемента.

53
00:02:53,010 --> 00:02:55,710
>> Так, у пошуках да права
крыху больш складана.

54
00:02:55,710 --> 00:03:00,170
Цяпер спачатку давайце разгледзім даўжыню
масіва на права

55
00:03:00,170 --> 00:03:01,240
сярэдні элемент.

56
00:03:01,240 --> 00:03:08,390
Так што, калі наш масіў быў памерам п, то
Новы масіў будзе мець памер н мінус

57
00:03:08,390 --> 00:03:10,140
сярэдні мінус 1.

58
00:03:10,140 --> 00:03:12,530
Такім чынам, давайце думаць пра н мінус сярэдзіне.

59
00:03:12,530 --> 00:03:18,710
>> Зноў жа, калі масіў былі памерам 20 і
мы дзелім на 2, каб атрымаць сярэдзіну,

60
00:03:18,710 --> 00:03:23,540
так сярэдзіна 10, то п мінус сярэдняга
збіраецца даць нам 10, дык 10

61
00:03:23,540 --> 00:03:25,330
элементы справа ад сярэдзіны.

62
00:03:25,330 --> 00:03:27,780
Але ў нас ёсць гэты мінус
1, так як мы не хочам, каб

63
00:03:27,780 --> 00:03:29,700
ўключаюць саму сярэдзіну.

64
00:03:29,700 --> 00:03:34,190
Так н мінус сярэдні мінус 1 дае нам
Агульная колькасць элементаў справа

65
00:03:34,190 --> 00:03:36,800
сярэдняга індэкса ў масіве.

66
00:03:36,800 --> 00:03:41,870
>> Цяпер вось, памятаеце, што сярэдні
параметрам з'яўляецца масіў значэнняў.

67
00:03:41,870 --> 00:03:46,180
Дык вось, мы перадаем
абнаўленне значэнні масіва.

68
00:03:46,180 --> 00:03:50,930
Гэтыя значэння плюс сярэдні плюс 1 з'яўляецца
фактычна кажучы рэкурсіўны выклік

69
00:03:50,930 --> 00:03:56,460
Пошук, пераходзячы ў новы масіў, дзе
што новы масіў пачынаецца ў сярэдзіне

70
00:03:56,460 --> 00:03:59,370
плюс адзін з нашых першапачатковых значэнняў масіва.

71
00:03:59,370 --> 00:04:05,400
>> Альтэрнатыўны сінтаксіс, што цяпер,
вы пачалі бачыць паказальнікі, з'яўляецца

72
00:04:05,400 --> 00:04:10,170
значэнні амперсенд сярэдняга плюс 1.

73
00:04:10,170 --> 00:04:17,149
Такім чынам, захапіць адрас сярэдзіне
плюс адзін элемент каштоўнасцяў.

74
00:04:17,149 --> 00:04:23,690
>> Цяпер, калі вы не былі зручныя
змены масіў, магчыма, вам

75
00:04:23,690 --> 00:04:28,900
можа таксама рэалізавалі гэта, выкарыстоўваючы
рэкурсіўны дапаможная функцыя, дзе

76
00:04:28,900 --> 00:04:31,680
што дапаможная функцыя прымае
больш аргументаў.

77
00:04:31,680 --> 00:04:36,610
Так замест таго, каб толькі значэнне,
масіў, і памер масіва,

78
00:04:36,610 --> 00:04:42,315
дапаможная функцыя можа заняць больш
аргументы, у тым ліку больш нізкім індэксам

79
00:04:42,315 --> 00:04:45,280
што вы клапоціцеся аб ў масіве
і верхні індэкс, што вы клапоціцеся

80
00:04:45,280 --> 00:04:46,300
аб масіве.

81
00:04:46,300 --> 00:04:49,770
>> І так адсочвання і ніжняя
індэкс і верхні індэкс, вы не

82
00:04:49,770 --> 00:04:52,780
трэба пастаянна змяняць
зыходныя значэнні масіва.

83
00:04:52,780 --> 00:04:56,390
Вы можаце проста працягваць
выкарыстоўваць масіў значэнняў.

84
00:04:56,390 --> 00:04:59,540
Але вось, звярніце ўвагу, мы не маем патрэбу ў памочніка
функцыянаваць да тых часоў, як мы

85
00:04:59,540 --> 00:05:01,760
гатовыя змяніць арыгінал
значэнні масіва.

86
00:05:01,760 --> 00:05:05,020
Мы гатовыя перадаць у
Абноўлены значэння.

87
00:05:05,020 --> 00:05:09,140
>> Зараз, мы не можам бінарны пошук па
масіў, які з'яўляецца малокомплектных.

88
00:05:09,140 --> 00:05:12,220
Такім чынам, давайце атрымаць гэтую разабрацца.

89
00:05:12,220 --> 00:05:17,650
Цяпер, звярніце ўвагу, што сартаванне апошнія два
параметры дзесятковага значэння, якое з'яўляецца

90
00:05:17,650 --> 00:05:21,110
Масіў, мы сартаванне і Int N,
што даўжыня масіва,

91
00:05:21,110 --> 00:05:22,250
мы сартавання.

92
00:05:22,250 --> 00:05:24,840
Такім чынам, вось мы хочам рэалізаваць
алгарытм сартавання

93
00:05:24,840 --> 00:05:26,690
што ёсць пра н у квадраце.

94
00:05:26,690 --> 00:05:30,560
Вы можаце выбраць бурбалка сартавання, адбору
сартаваць, або сартаванне ўстаўкамі, або

95
00:05:30,560 --> 00:05:32,670
некаторы іншы выгляд у нас не
бачыў у класе.

96
00:05:32,670 --> 00:05:36,380
Але тут, мы збіраемся
выкарыстоўваць выбару роду.

97
00:05:36,380 --> 00:05:40,030
>> Так, мы збіраемся ітэрацыі
на працягу ўсяго масіву.

98
00:05:40,030 --> 00:05:44,360
Ну, вось мы бачым, што мы ітэрацыі
ад 0 да п мінус 1.

99
00:05:44,360 --> 00:05:45,990
Чаму б не ўсе, аж да п?

100
00:05:45,990 --> 00:05:49,320
Ну, калі мы ўжо адсартаваныя першым
п мінус 1 элементаў, то

101
00:05:49,320 --> 00:05:54,420
самы апошні элемент, што ўжо павінна быць
ў правільным месцы, так сартавання па

102
00:05:54,420 --> 00:05:56,520
ўвесь масіў.

103
00:05:56,520 --> 00:05:58,770
>> Цяпер успомніце, як выбар
накшталт працуе.

104
00:05:58,770 --> 00:06:01,950
Мы збіраемся ісці на працягу ўсяго масіва
шукаю мінімальнага значэння ў

105
00:06:01,950 --> 00:06:04,480
масіў і перніка, што
у самым пачатку.

106
00:06:04,480 --> 00:06:07,610
Тады мы збіраемся ісці на працягу ўсяго
Масіў зноў шукае другога

107
00:06:07,610 --> 00:06:10,410
найменшы элемент, і палка, што
на другой пазіцыі ў

108
00:06:10,410 --> 00:06:12,100
масіў, і гэтак далей.

109
00:06:12,100 --> 00:06:14,330
Такім чынам, вось што гэта робіць.

110
00:06:14,330 --> 00:06:17,290
>> Тут мы бачым, што мы
ўстаноўкі бягучага мінімуму

111
00:06:17,290 --> 00:06:20,030
значэнне для г-га азначніка.

112
00:06:20,030 --> 00:06:23,160
Так на першай ітэрацыі, мы збіраемся
разгледзець мінімальнае значэнне быць

113
00:06:23,160 --> 00:06:25,030
пачатак нашага масіва.

114
00:06:25,030 --> 00:06:28,500
Тады, мы збіраемся для перабору
Астатняя частка масіва, праверка на

115
00:06:28,500 --> 00:06:31,870
ўбачыць, калі ёсць якія-небудзь элементы менш, чым
той, які мы ў цяперашні час

116
00:06:31,870 --> 00:06:33,900
улічваючы мінімум.

117
00:06:33,900 --> 00:06:38,840
>> Дык вось, значэнні J плюс адзін - гэта
менш, чым тое, што мы ў цяперашні час

118
00:06:38,840 --> 00:06:40,380
улічваючы мінімум.

119
00:06:40,380 --> 00:06:42,940
Тады мы збіраемся абнавіць тое, што
мы думаем, што гэта мінімальны, каб

120
00:06:42,940 --> 00:06:44,640
індэкс J плюс 1.

121
00:06:44,640 --> 00:06:48,540
Так, зрабіць гэта праз увесь масіў,
і пасля гэтага на працягу цыкла, мінімум

122
00:06:48,540 --> 00:06:53,160
павінна быць мінімальным элементам з
я-ю пазіцыю ў масіве.

123
00:06:53,160 --> 00:06:57,350
>> Як толькі ў нас ёсць, што мы можам памяняць
Мінімальнае значэнне ў г-й пазіцыі

124
00:06:57,350 --> 00:06:58,230
ў масіве.

125
00:06:58,230 --> 00:07:00,130
Так што гэта ўсяго толькі стандартны swap.

126
00:07:00,130 --> 00:07:03,940
Мы захоўваем у часовым значэнні -
значэнне я-я ў масіве -

127
00:07:03,940 --> 00:07:08,460
значэнне змяшчаецца г-й у масіве
Мінімальнае значэнне, якое належыць там,

128
00:07:08,460 --> 00:07:13,580
а затым захаваць назад у дзе
току мінімальнае значэнне раней

129
00:07:13,580 --> 00:07:16,460
I-й значэнне ў масіве, так
што мы не страцілі яго.

130
00:07:16,460 --> 00:07:20,510
>> Так, што працягваецца
наступная ітэрацыя.

131
00:07:20,510 --> 00:07:23,480
Мы пачнем шукаць другога
Мінімальнае значэнне і ўстаўце, што ў

132
00:07:23,480 --> 00:07:24,590
Другая пазіцыя.

133
00:07:24,590 --> 00:07:27,440
На трэцяй ітэрацыі, мы будзем шукаць
трэцяе значэнне мінімальнай і ўстаўка

134
00:07:27,440 --> 00:07:31,550
што ў трэцім становішчы, і таму
, Пакуль у нас няма адсартаваны масіў.

135
00:07:31,550 --> 00:07:33,820
Мяне клічуць Боб, і гэта
быў выбар роду.

136
00:07:33,820 --> 00:07:39,456