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
Ето, ние виждаме, Int стойност, която е
Предполага се, че стойността на потребителя е

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
И ние виждаме Int N, която е
дължината на нашия масив.

14
00:00:45,602 --> 00:00:47,410
>> Сега, първото нещо, което на първо място.

15
00:00:47,410 --> 00:00:51,350
Ние проверяваме дали N е равно на 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
Запомни последния параметър е нашата Int
N, така че е дължината на нашия масив.

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, разделено на две, това означава, че ние сме
прокарате 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
Така че, ако нашият масив е с размер N, тогава
Новата гама ще бъде с размер N минус

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
Така п минус средната минус едно ни е дава
общия брой на елементи на правото

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
Тези стойности плюс средната плюс едно е
всъщност казва рекурсивно обадите

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
амперсанд стойности средната плюс един.

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
Сега забелязвам, че нещо като е минало два
параметри INT стойности, който е

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
Е, ако вече сме подредени на първия
N минус 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
стойност на I-ия индекс.

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 плюс един.

121
00:06:44,640 --> 00:06:48,540
Така че, направи това през целия масив,
и след това в продължение на контур, минимално

122
00:06:48,540 --> 00:06:53,160
трябва да бъде минимум елемент от
I-та позиция в масива.

123
00:06:53,160 --> 00:06:57,350
>> След като имаме това, ние можем да сменяте
минимална стойност в позиция I-та

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
Ние съхраняваме във временно стойност -
стойността на I-та в масива -

127
00:07:03,940 --> 00:07:08,460
пусната в стойността на I-то място в масива
Минималната стойност, която принадлежи там,

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