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

2
00:00:13,300 --> 00:00:15,010
>> РОБ БОВДЕН: Здраво, ја сам Роб.

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
Ми видимо инт вредности низ, који
је низ у коме смо

12
00:00:40,800 --> 00:00:42,520
у потрази за вредношћу.

13
00:00:42,520 --> 00:00:45,602
И видимо инт н, који је
дужина нашег низа.

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
низ који смо сортирање, и инт н,
која је дужина низа који

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
>> Дакле овде, ј вредности плус један - то је
мање него што смо тренутно

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
индекс ј плус 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
Дакле, ово је само стандардни своп.

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
и-ти вредност у низу, тако
да нисмо га изгубити.

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