1
00:00:00,000 --> 00:00:03,346
>> [Играет музыка]

2
00:00:03,346 --> 00:00:05,258

3
00:00:05,258 --> 00:00:06,220
>> ДАГ Lloyd: Ладно.

4
00:00:06,220 --> 00:00:08,140
Так бинарный поиск является
Алгоритм можно использовать

5
00:00:08,140 --> 00:00:10,530
найти элемент внутри массива.

6
00:00:10,530 --> 00:00:14,710
В отличие от линейного поиска, он требует
особое состояние быть выполнены заранее,

7
00:00:14,710 --> 00:00:19,020
но это так гораздо более эффективным, если
это условие, на самом деле, встретились.

8
00:00:19,020 --> 00:00:20,470
>> Так что идея здесь?

9
00:00:20,470 --> 00:00:21,780
это разделяй и властвуй.

10
00:00:21,780 --> 00:00:25,100
Мы хотим, чтобы уменьшить размер
область поиска на половину каждого времени

11
00:00:25,100 --> 00:00:27,240
Чтобы найти номер адресата.

12
00:00:27,240 --> 00:00:29,520
Это где это условие
вступает в игру, хотя.

13
00:00:29,520 --> 00:00:32,740
Мы можем только использовать возможности
устраняя половины элементов

14
00:00:32,740 --> 00:00:36,070
даже не глядя на
им, если массив отсортирован.

15
00:00:36,070 --> 00:00:39,200
>> Если это полная путаница,
Мы не можем просто из рук

16
00:00:39,200 --> 00:00:42,870
отбросить половину элементов, так
мы не знаем, что мы отбрасывая.

17
00:00:42,870 --> 00:00:45,624
Но если массив отсортирован,
мы можем сделать это, потому что мы

18
00:00:45,624 --> 00:00:48,040
знать, что все в
оставили, где мы в настоящее время

19
00:00:48,040 --> 00:00:50,500
должна быть ниже, чем
значение мы в настоящее время.

20
00:00:50,500 --> 00:00:52,300
И все к
Право, где мы

21
00:00:52,300 --> 00:00:55,040
должна быть больше, чем значение
мы в настоящее время смотрит.

22
00:00:55,040 --> 00:00:58,710
>> Так что псевдокод
шаги для бинарного поиска?

23
00:00:58,710 --> 00:01:02,310
Мы повторяем этот процесс до тех пор,
массив или, как мы пройти через,

24
00:01:02,310 --> 00:01:07,740
суб массивы, мелкие кусочки
исходный массив, имеет размер 0.

25
00:01:07,740 --> 00:01:10,960
Рассчитать среднюю
текущего подобласти.

26
00:01:10,960 --> 00:01:14,460
>> Если значение, которое вы ищете,
в этом элементе массива, остановиться.

27
00:01:14,460 --> 00:01:15,030
Ты нашел это.

28
00:01:15,030 --> 00:01:16,550
Замечательно.

29
00:01:16,550 --> 00:01:19,610
В противном случае, если цель
меньше, чем то, что в середине,

30
00:01:19,610 --> 00:01:23,430
так что если значение, которое мы ищем
для меньше, чем то, что мы видим,

31
00:01:23,430 --> 00:01:26,780
повторить этот процесс еще раз, но
изменить конечную точку, а не

32
00:01:26,780 --> 00:01:29,300
бытия оригинал
завершить полный спектр,

33
00:01:29,300 --> 00:01:34,110
чтобы быть только слева
где мы просто смотрели.

34
00:01:34,110 --> 00:01:38,940
>> Мы знали, что средняя была слишком высокой,
или цель была меньше, чем в середине,

35
00:01:38,940 --> 00:01:42,210
и поэтому он должен существовать, если он
вообще существует в массиве,

36
00:01:42,210 --> 00:01:44,660
где в левой части середины.

37
00:01:44,660 --> 00:01:48,120
И поэтому мы будем устанавливать массив
место только для левой

38
00:01:48,120 --> 00:01:51,145
от средней точки в качестве нового конечного пункта.

39
00:01:51,145 --> 00:01:53,770
И наоборот, если цель
больше, чем то, что в середине,

40
00:01:53,770 --> 00:01:55,750
мы делаем точно такой же
процесс, но вместо этого мы

41
00:01:55,750 --> 00:01:59,520
изменить начальную точку, чтобы быть
только справа от середины

42
00:01:59,520 --> 00:02:00,680
мы только что вычислили.

43
00:02:00,680 --> 00:02:03,220
И тогда мы начинаем процесс снова.

44
00:02:03,220 --> 00:02:05,220
>> Давайте себе это, хорошо?

45
00:02:05,220 --> 00:02:08,620
Таким образом, есть много всего происходит, и здесь,
но вот массив из 15 элементов.

46
00:02:08,620 --> 00:02:11,400
И мы собираемся быть отслеживание
много больше вещей на этот раз.

47
00:02:11,400 --> 00:02:13,870
Таким образом, в линейном поиске, мы были
только заботясь о цели.

48
00:02:13,870 --> 00:02:15,869
Но в этот раз мы хотим, чтобы
заботиться о где мы

49
00:02:15,869 --> 00:02:18,480
начинает выглядеть, где
мы остановились, глядя,

50
00:02:18,480 --> 00:02:21,876
и то, что середина
текущего массива.

51
00:02:21,876 --> 00:02:23,250
Так вот мы идем с бинарного поиска.

52
00:02:23,250 --> 00:02:25,290
Мы довольно много хорошо идти, верно?

53
00:02:25,290 --> 00:02:28,650
Я просто хочу, чтобы положить вниз
ниже здесь множество индексов.

54
00:02:28,650 --> 00:02:32,430
Это в основном только то, что элемент
массива мы говорим о.

55
00:02:32,430 --> 00:02:34,500
При линейном поиске, мы
заботиться, поскольку мы

56
00:02:34,500 --> 00:02:36,800
нужно знать, сколько
элементы мы Перебор,

57
00:02:36,800 --> 00:02:40,010
но мы на самом деле не волнует, что
элемент в настоящее время мы смотрим.

58
00:02:40,010 --> 00:02:41,014
В бинарного поиска, мы делаем.

59
00:02:41,014 --> 00:02:42,930
И так те просто
там немного руководства.

60
00:02:42,930 --> 00:02:44,910
>> Таким образом, мы можем начать, правильно?

61
00:02:44,910 --> 00:02:46,240
Ну, не совсем.

62
00:02:46,240 --> 00:02:48,160
Помните, что я сказал,
о двоичного поиска?

63
00:02:48,160 --> 00:02:50,955
Мы не можем сделать это на
несортированный массив или еще,

64
00:02:50,955 --> 00:02:55,820
мы не гарантирует, что
некоторые элементы или значения не

65
00:02:55,820 --> 00:02:57,650
случайного
отбрасываются, когда мы просто

66
00:02:57,650 --> 00:02:59,920
решили игнорировать половина массива.

67
00:02:59,920 --> 00:03:02,574
>> Так шаг один с бинарного поиска
это вы должны иметь упорядоченный массив.

68
00:03:02,574 --> 00:03:05,240
И вы можете использовать любой из сортировки
алгоритмы мы говорили о

69
00:03:05,240 --> 00:03:06,700
чтобы вы на эту должность.

70
00:03:06,700 --> 00:03:10,370
Так что теперь, мы в таком положении, когда
мы можем выполнить бинарный поиск.

71
00:03:10,370 --> 00:03:12,560
>> Так давайте повторим процесс
шаг за шагом, и держите

72
00:03:12,560 --> 00:03:14,830
трек, что происходит, как мы идем.

73
00:03:14,830 --> 00:03:17,980
Таким образом, сначала мы должны сделать, это рассчитать
середина текущего массива.

74
00:03:17,980 --> 00:03:20,620
Ну, мы сказать, что мы, в первую
все, глядя на стоимость 19.

75
00:03:20,620 --> 00:03:22,290
Мы пытаемся, чтобы найти номер 19.

76
00:03:22,290 --> 00:03:25,380
Первый элемент этого
Массив расположен с индексом ноль,

77
00:03:25,380 --> 00:03:28,880
а последний элемент в этом
Массив расположен в индексе 14.

78
00:03:28,880 --> 00:03:31,430
И так мы будем называть тех, начало и конец.

79
00:03:31,430 --> 00:03:35,387
>> Таким образом, мы вычислить среднюю по
добавив 0 плюс 14 деленное на 2;

80
00:03:35,387 --> 00:03:36,720
довольно просто середина.

81
00:03:36,720 --> 00:03:40,190
И мы можем сказать, что
середина сейчас 7.

82
00:03:40,190 --> 00:03:43,370
Так 15 то, что мы ищем?

83
00:03:43,370 --> 00:03:43,940
Нет, это не так.

84
00:03:43,940 --> 00:03:45,270
Мы ищем 19.

85
00:03:45,270 --> 00:03:49,400
Но мы знаем, что 19 больше,
чем то, что мы нашли в середине.

86
00:03:49,400 --> 00:03:52,470
>> Итак, что мы можем сделать, это
изменить начальную точку

87
00:03:52,470 --> 00:03:57,280
чтобы быть просто справа от
середина, и повторить процесс снова.

88
00:03:57,280 --> 00:04:01,690
И когда мы это сделаем, мы теперь сказать
Новый старт точка расположения массива 8.

89
00:04:01,690 --> 00:04:07,220
То, что мы сделали это эффективно
игнорируются все слева от 15.

90
00:04:07,220 --> 00:04:09,570
Мы ликвидировали половину
проблемы, и в настоящее время,

91
00:04:09,570 --> 00:04:13,510
вместо того, чтобы искать
более 15 элементов в массиве,

92
00:04:13,510 --> 00:04:15,610
у нас есть только для поиска более 7.

93
00:04:15,610 --> 00:04:17,706
Так 8 является новый старт точка.

94
00:04:17,706 --> 00:04:19,600
14 по-прежнему является конечной точкой.

95
00:04:19,600 --> 00:04:21,430
>> А теперь, перейдем это снова.

96
00:04:21,430 --> 00:04:22,810
Мы вычисляем новое середину.

97
00:04:22,810 --> 00:04:27,130
8 плюс 14 22, делится на 2 11.

98
00:04:27,130 --> 00:04:28,660
Это то, что мы ищем?

99
00:04:28,660 --> 00:04:30,110
Нет, это не так.

100
00:04:30,110 --> 00:04:32,930
Мы ищем значению,
меньше, чем то, что мы только что нашли.

101
00:04:32,930 --> 00:04:34,721
Так что мы собираемся повторить
процесс снова.

102
00:04:34,721 --> 00:04:38,280
Мы собираемся изменить конечную точку для
как раз слева от середины.

103
00:04:38,280 --> 00:04:41,800
Таким образом, новый конечный пункт становится 10.

104
00:04:41,800 --> 00:04:44,780
А теперь, вот только часть
массив, мы должны разобраться в.

105
00:04:44,780 --> 00:04:48,460
Таким образом, мы уже устранены
12 из 15 элементов.

106
00:04:48,460 --> 00:04:51,550
Мы знаем, что, если 19
существует в массиве, это

107
00:04:51,550 --> 00:04:57,210
должен существовать где-то между элементом
№ 8 и № 10 элемент.

108
00:04:57,210 --> 00:04:59,400
>> Таким образом, мы вычисляем новое середину снова.

109
00:04:59,400 --> 00:05:02,900
8 плюс 10 18, делится на 2 9.

110
00:05:02,900 --> 00:05:05,074
И в этом случае, смотрите,
цель в середине.

111
00:05:05,074 --> 00:05:06,740
Мы нашли именно то, что мы ищем.

112
00:05:06,740 --> 00:05:07,780
Мы можем остановиться.

113
00:05:07,780 --> 00:05:10,561
Мы успешно завершили
двоичный поиск.

114
00:05:10,561 --> 00:05:11,060
Все в порядке.

115
00:05:11,060 --> 00:05:13,930
Итак, мы знаем этот алгоритм
работает, если цель

116
00:05:13,930 --> 00:05:16,070
где-то внутри массива.

117
00:05:16,070 --> 00:05:19,060
Означает ли это работать, если алгоритм
цель не в массиве?

118
00:05:19,060 --> 00:05:20,810
Ну, давайте начнем ее
снова, и на этот раз,

119
00:05:20,810 --> 00:05:23,380
давайте посмотрим на элемент
16, которые визуально видно,

120
00:05:23,380 --> 00:05:25,620
нигде не существует в массиве.

121
00:05:25,620 --> 00:05:27,110
>> Начальная точка снова 0.

122
00:05:27,110 --> 00:05:28,590
Конечная точка снова 14.

123
00:05:28,590 --> 00:05:32,490
Таковы показатели первого и
Последние элементы массива. полный

124
00:05:32,490 --> 00:05:36,057
И мы будем идти через процесс мы только
пошел через раз, пытаясь найти 16,

125
00:05:36,057 --> 00:05:39,140
даже если визуально, мы можем уже
сказать, что он не собирается быть там.

126
00:05:39,140 --> 00:05:43,450
Мы просто хотим, чтобы убедиться, что этот алгоритм
будет, на самом деле, до сих пор работают в какой-то мере

127
00:05:43,450 --> 00:05:46,310
и не просто оставить нам
застрял в бесконечном цикле.

128
00:05:46,310 --> 00:05:48,190
>> Так что шаг первым?

129
00:05:48,190 --> 00:05:50,230
Рассчитать среднюю
текущего массива.

130
00:05:50,230 --> 00:05:52,790
Что середина
текущего массива?

131
00:05:52,790 --> 00:05:54,410
Ну, это 7, верно?

132
00:05:54,410 --> 00:05:57,560
14 плюс 0 разделить на 2, 7.

133
00:05:57,560 --> 00:05:59,280
15 то, что мы ищем?

134
00:05:59,280 --> 00:05:59,780
Нет.

135
00:05:59,780 --> 00:06:02,930
Это довольно близко, но мы ищем
для значения немного больше, чем это.

136
00:06:02,930 --> 00:06:06,310
>> Итак, мы знаем, что это будет
не быть нигде слева 15.

137
00:06:06,310 --> 00:06:08,540
Целевое больше
что в середине.

138
00:06:08,540 --> 00:06:12,450
И поэтому мы устанавливаем новую начальную точку для
как раз справа от середины.

139
00:06:12,450 --> 00:06:16,130
Середина в настоящее время 7, так
скажем, новую начальную точку 8.

140
00:06:16,130 --> 00:06:18,130
И то, что мы фактически
сделать еще раз игнорируется

141
00:06:18,130 --> 00:06:21,150
вся левая половина массива.

142
00:06:21,150 --> 00:06:23,750
>> Теперь мы повторяем
обрабатывать еще раз.

143
00:06:23,750 --> 00:06:24,910
Рассчитать новую среднюю.

144
00:06:24,910 --> 00:06:29,350
8 плюс 14 22, делится на 2 11.

145
00:06:29,350 --> 00:06:31,060
23 то, что мы ищем?

146
00:06:31,060 --> 00:06:31,870
К сожалению нет.

147
00:06:31,870 --> 00:06:34,930
Мы ищем значение
что меньше, чем 23.

148
00:06:34,930 --> 00:06:37,850
И поэтому в данном случае, мы собираемся
изменить конечную точку, чтобы быть просто

149
00:06:37,850 --> 00:06:40,035
слева от текущего середине.

150
00:06:40,035 --> 00:06:43,440
В настоящее время средняя точка 11, и
поэтому мы зададим новую конечную точку

151
00:06:43,440 --> 00:06:46,980
в следующий раз мы идем
через этот процесс до 10.

152
00:06:46,980 --> 00:06:48,660
>> Опять же, мы идем через процесс снова.

153
00:06:48,660 --> 00:06:49,640
Рассчитать среднюю.

154
00:06:49,640 --> 00:06:53,100
8 плюс 10 делится на 2 9.

155
00:06:53,100 --> 00:06:54,750
Есть 19, что мы ищем?

156
00:06:54,750 --> 00:06:55,500
К сожалению нет.

157
00:06:55,500 --> 00:06:58,050
Мы все еще ищем
число меньше.

158
00:06:58,050 --> 00:07:02,060
Таким образом, мы изменить конечную точку на этот раз
быть просто слева от середины.

159
00:07:02,060 --> 00:07:05,532
Середина в настоящее время 9,
так что конечная точка будет 8.

160
00:07:05,532 --> 00:07:07,920
И теперь, мы просто ищем
в одном массиве элемента.

161
00:07:07,920 --> 00:07:10,250
>> Что середина этого массива?

162
00:07:10,250 --> 00:07:13,459
Ну, он начинается в 8, это
заканчивается в 8, середина 8.

163
00:07:13,459 --> 00:07:14,750
Это то, что мы ищем?

164
00:07:14,750 --> 00:07:16,339
Мы ищем 17?

165
00:07:16,339 --> 00:07:17,380
Нет, мы ищем 16.

166
00:07:17,380 --> 00:07:20,160
Так что, если он существует в массиве,
она должна где-то существовать

167
00:07:20,160 --> 00:07:21,935
слева, где мы в настоящее время.

168
00:07:21,935 --> 00:07:23,060
Так что же мы будем делать?

169
00:07:23,060 --> 00:07:26,610
Ну, мы установить конечную точку, чтобы быть просто
слева от текущего середине.

170
00:07:26,610 --> 00:07:29,055
Таким образом, мы изменить конечную точку до 7.

171
00:07:29,055 --> 00:07:32,120
Вы видите, что только
здесь произошло, правда?

172
00:07:32,120 --> 00:07:33,370
Посмотрите здесь.

173
00:07:33,370 --> 00:07:35,970
>> Начать сейчас больше, чем конец.

174
00:07:35,970 --> 00:07:39,620
Фактически, два конца
из нашего массива перешли,

175
00:07:39,620 --> 00:07:42,252
и начальная точка находится
Теперь после того, как в конечной точке.

176
00:07:42,252 --> 00:07:43,960
Ну, это не
никакого смысла, не так ли?

177
00:07:43,960 --> 00:07:47,960
Так что теперь, что мы можем сказать, что мы
есть суб массив размером 0.

178
00:07:47,960 --> 00:07:50,110
И как только мы добрались до
Эта точка зрения, мы можем в настоящее время

179
00:07:50,110 --> 00:07:53,940
гарантировать, что элемент 16
не существует в массиве,

180
00:07:53,940 --> 00:07:56,280
потому начальной точки
и конечная точка перешли.

181
00:07:56,280 --> 00:07:58,340
И таким образом это не там.

182
00:07:58,340 --> 00:08:01,340
Теперь, обратите внимание, что это немного
отличается от точки начала и окончания

183
00:08:01,340 --> 00:08:02,900
Суть в том, то же самое.

184
00:08:02,900 --> 00:08:05,030
Если бы мы были глядя
на 17, это было бы

185
00:08:05,030 --> 00:08:08,870
был в массиве, и точки старта
и конечная точка этого последней итерации

186
00:08:08,870 --> 00:08:11,820
прежде чем эти точки пересекаются,
мы бы нашли 17 там.

187
00:08:11,820 --> 00:08:15,510
Это только, когда они пересекают, что мы можем
гарантировать, что элемент не

188
00:08:15,510 --> 00:08:17,180
существует в массиве.

189
00:08:17,180 --> 00:08:20,260
>> Итак, давайте много меньше
шагов, чем линейный поиск.

190
00:08:20,260 --> 00:08:23,250
В худшем случае, мы имели
разделить список элементов п

191
00:08:23,250 --> 00:08:27,770
неоднократно в половине, чтобы найти цель,
либо потому, что целевой элемент

192
00:08:27,770 --> 00:08:33,110
будет где-то в последний
деление, или он не существует вообще.

193
00:08:33,110 --> 00:08:37,830
Таким образом, в худшем случае, мы должны
разделить на array-- вы знаете?

194
00:08:37,830 --> 00:08:40,510
Журнал п раз; мы
должны сократить проблемы

195
00:08:40,510 --> 00:08:42,610
в половине определенное количество раз.

196
00:08:42,610 --> 00:08:45,160
Это число раз является журнал п.

197
00:08:45,160 --> 00:08:46,510
>> Какой самый лучший сценарий?

198
00:08:46,510 --> 00:08:48,899
Ну, в первый раз мы
рассчитать среднюю,

199
00:08:48,899 --> 00:08:50,190
мы находим, что мы ищем.

200
00:08:50,190 --> 00:08:52,150
Во всех предыдущих
примеры на бинарный поиск

201
00:08:52,150 --> 00:08:55,489
мы только что закончилась, если бы мы имели
искал элемента 15,

202
00:08:55,489 --> 00:08:57,030
мы обнаружили, что немедленно.

203
00:08:57,030 --> 00:08:58,321
Это было в самом начале.

204
00:08:58,321 --> 00:09:01,200
Это было середина
первая попытка раскола

205
00:09:01,200 --> 00:09:03,950
дивизии в бинарный поиск.

206
00:09:03,950 --> 00:09:06,350
>> И так в худшем
так, бинарный поиск работает

207
00:09:06,350 --> 00:09:11,580
в журнале п, что значительно лучше,
чем линейный поиск, в худшем случае.

208
00:09:11,580 --> 00:09:16,210
В лучшем случае, двоичный
Поиск работает омега 1.

209
00:09:16,210 --> 00:09:18,990
Так бинарный поиск много
лучше, чем линейный поиск,

210
00:09:18,990 --> 00:09:23,270
но вам приходится иметь дело с процессом
сортировка свой массив, прежде чем вы можете

211
00:09:23,270 --> 00:09:26,140
использовать силу двоичного поиска.

212
00:09:26,140 --> 00:09:27,130
>> Я Дуг Ллойд.

213
00:09:27,130 --> 00:09:29,470
Это CS 50.

214
00:09:29,470 --> 00:09:31,070