1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Двійковий пошук]

2
00:00:02,000 --> 00:00:04,000
[Патрік Шмід - Гарвардський університет]

3
00:00:04,000 --> 00:00:07,000
[Це CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Якби я дав вам список імен Діснея характеру в алфавітному порядку

5
00:00:09,000 --> 00:00:11,000
і запитав, чи можна знайти Міккі Мауса,

6
00:00:11,000 --> 00:00:13,000
як би ви про це?

7
00:00:13,000 --> 00:00:15,000
Один з очевидних шляхів було б переглянути список із самого початку

8
00:00:15,000 --> 00:00:18,000
і перевірте кожне ім'я, щоб побачити, якщо це Міккі.

9
00:00:18,000 --> 00:00:22,000
Але, як ви читаєте Aladdin, Аліса, Аріель, і так далі,

10
00:00:22,000 --> 00:00:25,000
Ви швидко зрозумієте, що, починаючи з передньої частини списку не було хорошою ідеєю.

11
00:00:25,000 --> 00:00:29,000
Гаразд, може бути, ви повинні почати працювати в зворотному напрямку від кінця списку.

12
00:00:29,000 --> 00:00:33,000
Зараз ви читаєте Тарзан, стібка, Білосніжка, і так далі.

13
00:00:33,000 --> 00:00:36,000
Тим не менш, це не здається, що кращий спосіб це зробити.

14
00:00:36,000 --> 00:00:38,000
>> Ну, ще один спосіб, що ви могли б іти про це, щоб спробувати звузити

15
00:00:38,000 --> 00:00:41,000
список імен, які у вас є на що подивитися.

16
00:00:41,000 --> 00:00:43,000
Оскільки ви знаєте, що вони розташовані в алфавітному порядку,

17
00:00:43,000 --> 00:00:45,000
Ви просто подивіться на імена в середині списку

18
00:00:45,000 --> 00:00:49,000
і перевірити, якщо Міккі Мауса до або після цього імені.

19
00:00:49,000 --> 00:00:51,000
Дивлячись на прізвище у другому стовпці

20
00:00:51,000 --> 00:00:54,000
ви б зрозуміли, що M Міккі приходить після J для Жасмин,

21
00:00:54,000 --> 00:00:57,000
так що вам просто ігнорувати першій половині списку.

22
00:00:57,000 --> 00:00:59,000
Тоді ви, напевно, подивіться на верхню частину останнього стовпця

23
00:00:59,000 --> 00:01:02,000
і бачу, що вона починається з Рапунцель.

24
00:01:02,000 --> 00:01:06,000
Міккі доходить до Рапунцель, схоже, що ми можемо ігнорувати останній колонці, а також.

25
00:01:06,000 --> 00:01:08,000
Продовжуючи стратегію пошуку, ви швидко зрозумієте, що Міккі

26
00:01:08,000 --> 00:01:11,000
У першій половині залишився списку імен

27
00:01:11,000 --> 00:01:14,000
і, нарешті, знайти Міккі ховається між Мерліном і Мінні.

28
00:01:14,000 --> 00:01:17,000
>> Те, що ви тільки що зробили був у основному бінарного пошуку.

29
00:01:17,000 --> 00:01:22,000
Як це випливає з назви, вона виконує свою стратегію пошуку в бінарному питання.

30
00:01:22,000 --> 00:01:24,000
Що це значить?

31
00:01:24,000 --> 00:01:27,000
Ну, дали список відсортованих елементів, алгоритм бінарного пошуку робить двійкових рішень -

32
00:01:27,000 --> 00:01:33,000
вліво або вправо, більше або менше, в алфавітному порядку, до або після - в кожній точці.

33
00:01:33,000 --> 00:01:35,000
Тепер у нас є ім'я, яке йде разом з цим алгоритм пошуку,

34
00:01:35,000 --> 00:01:38,000
Давайте подивимося на інший приклад, але на цей раз зі списком відсортовані номери.

35
00:01:38,000 --> 00:01:43,000
Скажімо, ми шукаємо число 144 у цьому списку відсортовані номери.

36
00:01:43,000 --> 00:01:46,000
Як і раніше, ми знаходимо число, яке знаходиться в середині -

37
00:01:46,000 --> 00:01:50,000
який в даному випадку складає 13 - і подивитися, якщо 144 більше або менше, ніж 13.

38
00:01:50,000 --> 00:01:54,000
Так як це явно більше, ніж 13, ми можемо ігнорувати все, що становить 13 або менше

39
00:01:54,000 --> 00:01:57,000
і просто зосередитися на половину, що залишилася.

40
00:01:57,000 --> 00:01:59,000
Так як у нас тепер є парне число предмети, залишені,

41
00:01:59,000 --> 00:02:01,000
Ми просто вибрати число, яке ближче до середини.

42
00:02:01,000 --> 00:02:03,000
У цьому випадку ми вибираємо 55.

43
00:02:03,000 --> 00:02:06,000
Ми могли б так само легко обрані 89.

44
00:02:06,000 --> 00:02:11,000
Добре. Знову ж, 144 більше, ніж 55, так що ми йдемо направо.

45
00:02:11,000 --> 00:02:14,000
На щастя для нас, наступне число є середнім 144,

46
00:02:14,000 --> 00:02:16,000
той, який ми шукаємо.

47
00:02:16,000 --> 00:02:21,000
Так що для того, щоб знайти 144 з допомогою двійкового пошуку, ми можемо знайти його лише у 3 етапи.

48
00:02:21,000 --> 00:02:24,000
Якби ми використовували лінійний пошук тут, це зайняло б нам 12 кроків.

49
00:02:24,000 --> 00:02:28,000
У самому справі, так як цей метод пошуку половинки кількість елементів

50
00:02:28,000 --> 00:02:31,000
він повинен дивитися на на кожному кроці, він знайде елемент, він шукає

51
00:02:31,000 --> 00:02:35,000
приблизно в журнал число елементів у списку.

52
00:02:35,000 --> 00:02:37,000
Тепер, коли ми бачили 2 приклади, давайте поглянемо на

53
00:02:37,000 --> 00:02:41,000
деякі псевдокод рекурсивну функцію, яка реалізує бінарний пошук.

54
00:02:41,000 --> 00:02:44,000
Починаючи з верхнього, ми бачимо, що ми повинні знайти функцію, яка приймає 4 аргументу:

55
00:02:44,000 --> 00:02:47,000
ключ, масив, хв, макс.

56
00:02:47,000 --> 00:02:51,000
Ключ це число, яке ми шукаємо, тому 144 в попередньому прикладі.

57
00:02:51,000 --> 00:02:54,000
Масив являє собою список чисел, які ми шукаємо.

58
00:02:54,000 --> 00:02:57,000
Мінімальна і максимальна є показники мінімальної і максимальної позиції

59
00:02:57,000 --> 00:02:59,000
що ми зараз дивимося.

60
00:02:59,000 --> 00:03:03,000
Тому, коли ми почнемо, хв буде дорівнює нулю і Макс буде максимальним індексом масиву.

61
00:03:03,000 --> 00:03:07,000
Як звузити пошук вниз, ми будемо оновлювати мінімальне і максимальне

62
00:03:07,000 --> 00:03:10,000
бути тільки діапазон, який ми все ще шукаємо дюйма

63
00:03:10,000 --> 00:03:12,000
>> Давайте переходити до цікавої частини першої.

64
00:03:12,000 --> 00:03:14,000
Перше, що нам зробити, це знайти середину,

65
00:03:14,000 --> 00:03:19,000
індекс, який знаходиться на півдорозі між мінімальною і максимальною масиву, що ми як і раніше розглядаємо.

66
00:03:19,000 --> 00:03:22,000
Тоді ми подивимося на значення масиву в той середина розташування

67
00:03:22,000 --> 00:03:25,000
і подивитися, якщо число, яке ми шукаємо менше, ніж ключ.

68
00:03:25,000 --> 00:03:27,000
Якщо число в цій позиції менше,

69
00:03:27,000 --> 00:03:31,000
то це означає, що ключ більше, ніж всі номери ліворуч від цієї позиції.

70
00:03:31,000 --> 00:03:33,000
Таким чином, ми можемо назвати бінарної функції пошуку знову,

71
00:03:33,000 --> 00:03:36,000
але на цей раз оновленню мінімальних і максимальних параметрів прочитати тільки половину

72
00:03:36,000 --> 00:03:40,000
, Що більше або дорівнює значенню ми тільки що розглянули.

73
00:03:40,000 --> 00:03:44,000
З іншого боку, якщо ключ менше, ніж число в поточному середині масиву,

74
00:03:44,000 --> 00:03:47,000
Ми хочемо, щоб піти наліво і ігнорувати всі числа, які більше.

75
00:03:47,000 --> 00:03:52,000
Знову ж таки, ми називаємо бінарний пошук, але на цей раз з діапазон мінімальних і максимальних оновлення

76
00:03:52,000 --> 00:03:54,000
, Щоб включити тільки нижню половину.

77
00:03:54,000 --> 00:03:57,000
Якщо значення на нинішньому середині масиву не є ні

78
00:03:57,000 --> 00:04:01,000
більше, ні менше, ніж ключ, то вона повинна бути дорівнює ключ.

79
00:04:01,000 --> 00:04:05,000
Таким чином, ми можемо просто повернути поточний індекс середину, і ми зробили.

80
00:04:05,000 --> 00:04:09,000
Нарешті, ця перевірка тут для випадку, коли число

81
00:04:09,000 --> 00:04:11,000
насправді не в масив чисел ми шукаємо.

82
00:04:11,000 --> 00:04:14,000
Якщо максимальний індекс діапазону, який ми шукаємо

83
00:04:14,000 --> 00:04:17,000
це все менше мінімуму, це означає, що ми зайшли надто далеко.

84
00:04:17,000 --> 00:04:20,000
Оскільки число не було у вхідному масиві, ми повертають -1

85
00:04:20,000 --> 00:04:24,000
щоб показати, що нічого не було знайдено.

86
00:04:24,000 --> 00:04:26,000
>> Ви, можливо, помітили, що для цього алгоритму на роботу,

87
00:04:26,000 --> 00:04:28,000
Список номерів повинен бути відсортований.

88
00:04:28,000 --> 00:04:31,000
Іншими словами, ми можемо знайти тільки 144 з допомогою бінарного пошуку

89
00:04:31,000 --> 00:04:34,000
якщо всі числа впорядковані від нижчого до вищого.

90
00:04:34,000 --> 00:04:38,000
Якби це було не так, ми не змогли б виключити половину номерів на кожному кроці.

91
00:04:38,000 --> 00:04:40,000
Тому у нас є 2 варіанти.

92
00:04:40,000 --> 00:04:43,000
Або ми можемо взяти несортоване список і відсортувати його перед використанням бінарного пошуку,

93
00:04:43,000 --> 00:04:48,000
або ми можемо переконатися, що список чисел сортуються по мірі додавання номера до неї.

94
00:04:48,000 --> 00:04:50,000
Таким чином, замість сортування тільки тоді, коли ми повинні шукати,

95
00:04:50,000 --> 00:04:53,000
чому б не зберегти список, відсортований у всі часи?

96
00:04:53,000 --> 00:04:57,000
>> Один із способів зберегти список номерів відсортовані одночасно дозволяючи

97
00:04:57,000 --> 00:04:59,000
, Щоб додати або перемістити номери з цього списку

98
00:04:59,000 --> 00:05:02,000
є використання так званих бінарних дерев пошуку.

99
00:05:02,000 --> 00:05:05,000
Дерево двійкового пошуку є структурою даних, яка має 3 властивості.

100
00:05:05,000 --> 00:05:09,000
По-перше, лівого піддерева будь-якого вузла містить лише значення, які менше

101
00:05:09,000 --> 00:05:11,000
або рівне значення вузла.

102
00:05:11,000 --> 00:05:15,000
По-друге, праве піддерево вузла містить лише значення, які більше

103
00:05:15,000 --> 00:05:17,000
або рівне значення вузла.

104
00:05:17,000 --> 00:05:20,000
І, нарешті, як ліве і праве піддерев всіх вузлів

105
00:05:20,000 --> 00:05:23,000
Також бінарні дерева пошуку.

106
00:05:23,000 --> 00:05:26,000
Давайте подивимося на приклад з тими ж номерами ми використовували раніше.

107
00:05:26,000 --> 00:05:30,000
Для тих з вас, хто ніколи не бачив дерево інформатики і раніше,

108
00:05:30,000 --> 00:05:34,000
Дозвольте мені почати з розповіді про те, що дерево комп'ютерні науки росте вниз.

109
00:05:34,000 --> 00:05:36,000
Так, на відміну від дерев ви звикли,

110
00:05:36,000 --> 00:05:38,000
корінь дерева, комп'ютерні науки знаходиться на вершині,

111
00:05:38,000 --> 00:05:41,000
і листя в нижній частині.

112
00:05:41,000 --> 00:05:45,000
Кожна коробочка називається вузлом, а вузли з'єднані один з одним по краях.

113
00:05:45,000 --> 00:05:48,000
Так що корінь цього дерева є вузлом значення з значенням 13,

114
00:05:48,000 --> 00:05:52,000
який має 2 дітей вузлів зі значеннями 5 і 34.

115
00:05:52,000 --> 00:05:57,000
Піддерево дерева, який утворюється, просто глянувши на підрозділ всього дерева.

116
00:05:57,000 --> 00:06:03,000
>> Наприклад, ліве піддерево вузла 3 є деревом створені вузли 0, 1, і 2.

117
00:06:03,000 --> 00:06:06,000
Таким чином, якщо ми повернемося до властивостей бінарне дерево пошуку,

118
00:06:06,000 --> 00:06:09,000
ми бачимо, що кожному вузлу в дереві відповідає всім 3 властивості, а саме:

119
00:06:09,000 --> 00:06:15,000
ліве піддерево містить лише значення, які менше або дорівнює значенню вузла;

120
00:06:15,000 --> 00:06:16,000
праве піддерево всіх вузлів

121
00:06:16,000 --> 00:06:19,000
містить лише значення, які більше або дорівнює значенню вузла, а

122
00:06:19,000 --> 00:06:25,000
лівого та правого піддерев всіх вузлів і дерева бінарного пошуку.

123
00:06:25,000 --> 00:06:28,000
Хоча це дерево виглядає по-іншому, це дійсно бінарне дерево пошуку

124
00:06:28,000 --> 00:06:30,000
за той же набір чисел.

125
00:06:30,000 --> 00:06:32,000
В Насправді, існує безліч можливих способів, які ви можете створити

126
00:06:32,000 --> 00:06:35,000
дійсний бінарне дерево пошуку з цих номерів.

127
00:06:35,000 --> 00:06:38,000
Ну, давайте повернемося до першого ми створили.

128
00:06:38,000 --> 00:06:40,000
Так що ми можемо зробити з цими деревами?

129
00:06:40,000 --> 00:06:44,000
Ну, ми можемо дуже просто знайти мінімальне і максимальне значення.

130
00:06:44,000 --> 00:06:46,000
Мінімальні значення можна знайти завжди буде лівий

131
00:06:46,000 --> 00:06:48,000
поки більше немає вузлів для відвідування.

132
00:06:48,000 --> 00:06:53,000
І навпаки, щоб знайти максимальний просто просто спускається до правої в кожен момент часу.

133
00:06:54,000 --> 00:06:56,000
>> Пошук будь-який інший номер, який не є мінімальним або максимальним

134
00:06:56,000 --> 00:06:58,000
Настільки ж легко.

135
00:06:58,000 --> 00:07:00,000
Сказати, що ми шукаємо число 89.

136
00:07:00,000 --> 00:07:03,000
Ми просто перевіряємо значення кожного вузла і піти наліво або направо,

137
00:07:03,000 --> 00:07:06,000
в залежності від того, значення вузла менше або більше, ніж

138
00:07:06,000 --> 00:07:08,000
той, який ми шукаємо.

139
00:07:08,000 --> 00:07:11,000
Таким чином, починаючи з кореня із 13, ми бачимо, що 89 більше,

140
00:07:11,000 --> 00:07:13,000
і тому ми йдемо направо.

141
00:07:13,000 --> 00:07:16,000
Тоді ми бачимо, вузол 34, і ми знову йдемо направо.

142
00:07:16,000 --> 00:07:20,000
89 є ще більшою, ніж 55, так що ми продовжуємо йти з правого боку.

143
00:07:20,000 --> 00:07:24,000
Ми тоді придумали вузол із значенням 144 і йдемо наліво.

144
00:07:24,000 --> 00:07:26,000
І ось, 89 тут же.

145
00:07:26,000 --> 00:07:31,000
>> Інша справа, що ми можемо зробити, це роздрукувати всі числа, виконуючи симетричного обходу.

146
00:07:31,000 --> 00:07:35,000
Симетричного обходу означає друкувати все, що в лівому піддереві

147
00:07:35,000 --> 00:07:37,000
з наступним друком самого вузла

148
00:07:37,000 --> 00:07:40,000
, А потім з наступним друком все в правому піддереві.

149
00:07:40,000 --> 00:07:43,000
Наприклад, давайте візьмемо наш улюблений бінарне дерево пошуку

150
00:07:43,000 --> 00:07:46,000
і роздрукувати числа в відсортованому порядку.

151
00:07:46,000 --> 00:07:49,000
Ми починаємо в корені 13, але перед друком 13 маємо роздрукувати

152
00:07:49,000 --> 00:07:51,000
всі в лівому піддереві.

153
00:07:51,000 --> 00:07:55,000
Таким чином, ми йдемо до 5. Ми повинні ще глибше вниз по дереву, доки не знайдемо самий лівий вузол,

154
00:07:55,000 --> 00:07:57,000
яка дорівнює нулю.

155
00:07:57,000 --> 00:08:00,000
Після друку нулю, ми повертаємося до 1 і надрукувати це.

156
00:08:00,000 --> 00:08:03,000
Тоді ми йдемо до праве піддерево, що на 2, і друкувати це.

157
00:08:03,000 --> 00:08:05,000
Тепер, коли ми закінчили з цього піддерева,

158
00:08:05,000 --> 00:08:07,000
ми можемо повернутися до 3 і роздрукувати його.

159
00:08:07,000 --> 00:08:11,000
Продовжуючи назад, ми виводимо 5, а потім 8.

160
00:08:11,000 --> 00:08:13,000
Тепер, коли ми завершили всі ліве піддерево,

161
00:08:13,000 --> 00:08:17,000
ми можемо надрукувати з 13-и почати працювати на праве піддерево.

162
00:08:17,000 --> 00:08:21,000
Ми хопу до 34, але перед друком 34, ми повинні роздрукувати його лівого піддерева.

163
00:08:21,000 --> 00:08:27,000
Таким чином, ми роздрукувати 21, то ми отримаємо роздрукувати 34, і відвідати його правого піддерева.

164
00:08:27,000 --> 00:08:31,000
З 55 не має лівого піддерева, ми роздрукувати його і переходите до своїх правому піддереві.

165
00:08:31,000 --> 00:08:36,000
144 має ліве піддерево, і тому ми роздрукувати 89, потім 144,

166
00:08:36,000 --> 00:08:39,000
і, нарешті, самого правого вузла 233.

167
00:08:39,000 --> 00:08:44,000
Там ви маєте його, всі номери друкуються в порядку від нижчого до вищого.

168
00:08:44,000 --> 00:08:47,000
>> Додавання щось в дерево є відносно безболісно, ​​а також.

169
00:08:47,000 --> 00:08:51,000
Все, що нам потрібно зробити, це переконатися, що ми дотримуємося 3 двійкових властивості дерева пошуку

170
00:08:51,000 --> 00:08:53,000
, А потім вставити значення, де є простір.

171
00:08:53,000 --> 00:08:55,000
Припустимо, ми хочемо, щоб вставити значення 7.

172
00:08:55,000 --> 00:08:58,000
З 7 менше, ніж 13, ми йдемо наліво.

173
00:08:58,000 --> 00:09:01,000
Але це більше 5, так що ми рухаємося вправо.

174
00:09:01,000 --> 00:09:04,000
Оскільки це менше 8 і 8 листовим вузлом, ми додаємо 7 до лівого дитини 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Ми додали ряд наших бінарне дерево пошуку.

176
00:09:09,000 --> 00:09:12,000
>> Якщо ми можемо додати речі, ми краще мати можливість видалити речі.

177
00:09:12,000 --> 00:09:14,000
На жаль для нас, видалення трохи складніше -

178
00:09:14,000 --> 00:09:16,000
Не багато, але тільки трохи.

179
00:09:16,000 --> 00:09:18,000
Є 3 різних сценаріїв, які ми повинні розглянути

180
00:09:18,000 --> 00:09:21,000
При видаленні елемента із двійкового дерева пошуку.

181
00:09:21,000 --> 00:09:24,000
Перший, найпростіший випадок, що елемент є кінцевим вузлом.

182
00:09:24,000 --> 00:09:27,000
У цьому випадку, ми просто видалити його і повернемося до нашого бізнесу.

183
00:09:27,000 --> 00:09:30,000
Скажімо, ми хочемо, щоб видалити 7, які ми тільки що додали.

184
00:09:30,000 --> 00:09:34,000
Ну, ми просто знайти його, видалити його, от і все.

185
00:09:35,000 --> 00:09:37,000
Наступний випадок, якщо вузол має тільки 1 дитина.

186
00:09:37,000 --> 00:09:40,000
Тут ми можемо видалити вузол, але спочатку ми повинні переконатися, що

187
00:09:40,000 --> 00:09:42,000
Для підключення піддерево, що в даний час залишила без батьків

188
00:09:42,000 --> 00:09:44,000
на батьківський вузол, який ми тільки що видалили.

189
00:09:44,000 --> 00:09:47,000
Скажімо, ми хочемо видалити 3 з нашого дерева.

190
00:09:47,000 --> 00:09:50,000
Ми дочірній елемент цього вузла і прикріпити його до батька вузла.

191
00:09:50,000 --> 00:09:54,000
У цьому випадку, ми зараз кріплення від 1 до 5.

192
00:09:54,000 --> 00:09:57,000
Це працює без проблем, тому що ми знаємо, у відповідності з деревом власності бінарний пошук,

193
00:09:57,000 --> 00:10:01,000
що все в лівому піддереві 3 була менше 5.

194
00:10:01,000 --> 00:10:05,000
Тепер, коли 3 в піддереві піклуються, ми можемо видалити його.

195
00:10:05,000 --> 00:10:08,000
Третій і останній випадок є найскладнішим.

196
00:10:08,000 --> 00:10:11,000
Це той випадок, коли вузол ми хочемо видалити має 2 дітей.

197
00:10:11,000 --> 00:10:15,000
Для того, щоб зробити це, ми повинні спочатку знайти вузол, який має найбільше значення,

198
00:10:15,000 --> 00:10:18,000
поміняти місцями два, а потім видалити вузол в питанні.

199
00:10:18,000 --> 00:10:22,000
Зверніть увагу на вузол, який має найбільше значення не може мати 2 дітей сама

200
00:10:22,000 --> 00:10:26,000
З його лівого дитина буде кращим кандидатом для наступної великої.

201
00:10:26,000 --> 00:10:30,000
Таким чином, видалення вузла з 2 дітьми зводиться до перекачування 2 вузлів,

202
00:10:30,000 --> 00:10:33,000
а потім видалити обробляється 1 з 2 вищезазначеного правила.

203
00:10:33,000 --> 00:10:37,000
Наприклад, припустимо, що ми хочемо, щоб видалити кореневий вузол, 13.

204
00:10:37,000 --> 00:10:39,000
Перше, що ми робимо, ми знаходимо найбільше значення в дерево

205
00:10:39,000 --> 00:10:41,000
який, в даному випадку, 21.

206
00:10:41,000 --> 00:10:46,000
Потім поміняйте місцями 2 вузлів, рішень 13 листків і 21 центрального вузла групи.

207
00:10:46,000 --> 00:10:49,000
Тепер ми можемо просто видалити 13.

208
00:10:50,000 --> 00:10:53,000
>> Як згадувалося раніше, існує безліч можливих способів зробити дійсно бінарне дерево пошуку.

209
00:10:53,000 --> 00:10:56,000
На жаль для нас, деякі з них гірше, ніж інші.

210
00:10:56,000 --> 00:10:59,000
Наприклад, що станеться, коли ми будуємо бінарне дерево пошуку

211
00:10:59,000 --> 00:11:01,000
від відсортований список чисел?

212
00:11:01,000 --> 00:11:04,000
Всі номери просто додав до права на кожному кроці.

213
00:11:04,000 --> 00:11:06,000
Коли ми хочемо знайти номер,

214
00:11:06,000 --> 00:11:08,000
у нас немає вибору, але тільки щоб подивитися на праві на кожному кроці.

215
00:11:08,000 --> 00:11:11,000
Це не краще, ніж лінійний пошук на всіх.

216
00:11:11,000 --> 00:11:13,000
Хоча ми не будемо розглядати їх тут, є й інші, більш складні,

217
00:11:13,000 --> 00:11:16,000
структури даних, щоб переконатися, що цього не станеться.

218
00:11:16,000 --> 00:11:18,000
Тим не менш, одну просту річ, що можна зробити, щоб уникнути цього,

219
00:11:18,000 --> 00:11:21,000
просто випадково перемішати вхідних значень.

220
00:11:21,000 --> 00:11:26,000
Малоймовірно, що по випадковості перетасував список чисел сортується.

221
00:11:26,000 --> 00:11:29,000
Якби це було так, казино не буде залишатися в бізнесі надовго.

222
00:11:29,000 --> 00:11:31,000
>> Там у Вас є це.

223
00:11:31,000 --> 00:11:34,000
Тепер ви знаєте про бінарних дерев пошуку та бінарний пошук.

224
00:11:34,000 --> 00:11:36,000
Я Патрік Шмід, і це CS50.

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
Один з очевидних способів буде сканувати список з ... [сигнал]

227
00:11:43,000 --> 00:11:46,000
... Кількість елементів ... да

228
00:11:46,000 --> 00:11:50,000
[Сміється]

229
00:11:50,000 --> 00:11:55,000
... Опублікувати вузла 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Ура! Це було -