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
>> DOUG 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
>> のがOK、これを視覚化してみましょうか？

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
>> だから、二分探索で1ステップ
あなたがソートされた配列を持っている必要があります。

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
この最初の要素
配列は、インデックス0に配置されています

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プラス2で割っ14を追加します。

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は、2で割った、22で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
だから我々は今排除しました
15の要素12。

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は、2で割った、18で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
2で割った14プラス0は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
>> 今、私たちは繰り返し
1より多くの時間を処理します。

143
00:06:23,750 --> 00:06:24,910
新しい中間点を計算します。

144
00:06:24,910 --> 00:06:29,350
8プラス14は、2で割った、22で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
2で割った8 + 10は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
最悪のシナリオでは、我々は持っていました
n個の要素のリストを分割します

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
n回のログ。我々
問題をカットする必要があります

195
00:08:40,510 --> 00:08:42,610
時間の半分の一定数インチ

196
00:08:42,610 --> 00:08:45,160
その回数は、ログnです。

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
実質的に良好であるログnは、内
最悪の場合には、線形探索より。

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