>> [音乐播放]
>> DOUG LLOYD：好吧。
所以二进制搜索是一个 算法，我们可以用
找到一个阵列中的元素。
与线性搜索，它需要一个 特殊情况事先满足，
但它是如此，如果更有效 该条件是，实际上，满足。
>> 那么，有什么想法吗？
这是分而治之。
我们要减少的大小 半每次由搜索区域
为了找到一个目标数。
这是该条件 进场时，虽然。
我们只能充分利用的力量 元素的消除半
连看都没看一眼 他们如果数组排序。
>> 如果它是一个完整的组合起来， 我们不能只是伸出手
丢弃一半的元件，因为 我们不知道我们正在抛弃。
但是，如果该数组排序， 我们可以做到这一点，因为我们
知道这一切的 在那里，我们目前还剩下
必须比低 价值我们目前在。
所有的一切都为 正确的我们在哪里
必须大于该值 我们目前正在观察。
>> 那么什么是伪 对于二进制搜索的步骤？
我们重复这个过程，直到 阵列或者，当我们继续完成，
子阵列，小件 原来的数组，是大小为0。
计算中点 当前子阵列。
>> 如果你正在寻找的价值 在该阵列的该元素，停止。
你发现了它。
那很棒。
否则，如果目标是 小于什么在中间，
因此，如果该值，我们正在寻找 对于比我们所看到的低，
再次重复此过程，但 改变结束点，而不是
被原 完成全阵列，
要到左边 在那里，我们只是看着。
>> 我们知道，中间的太高， 或目标是小于中间，
因此它必须存在，如果它 在所有存在于所述阵列，
某处中点的左侧。
因此，我们将设置阵列 位置到左边
的中点作为新的终点。
相反，如果所述目标是 大于什么在中间，
我们做同样的 过程，而是我们
更改开始点为 只是为了中点的右
我们刚刚计算。
然后，我们再开始这个过程。
>> 让我们想象这样好不好？
所以这是一个很多事情，并就到这里， 但这里的15个元素的数组。
而我们将要被跟踪 对很多更多的东西这个时候。
因此，在线性搜索，我们 只是关心的目标。
但是这一次，我们要 关心我们在哪里
在那里开始寻找， 在我们停止寻找，
什么是中点 目前阵。
所以在这里，我们一起去二进制搜索。
我们非常好走，对不对？
我只是要放下 下面在这里一组指标。
这基本上是哪些因素 数组的，我们正在谈论。
随着线性搜索，我们 关心，因为我们
需要知道多少 我们迭代的元素，
但我们并不真正关心什么 元素，我们目前正在观察。
在二进制搜索，我们做的。
所以这些只是 有作为一个小导游。
>> 因此，我们可以开始了吧？
好了，不完全是。
还记得我说的 关于二进制搜索？
我们不能上做 排序的数组否则，
我们不低保 某些元素或值是不
被意外 丢弃的时候，我们刚刚
决定忽略一半阵列。
>> 因此，与二进制搜索第一步 是你必须有一个排序的数组。
你可以使用任何排序 我们已经讨论过的算法
让你到那个位置。
所以，现在，我们正处在一个位置， 我们可以执行二进制搜索。
>> 因此，让我们重复这个过程 一步一步，并保持
轨道发生了什么，因为我们去。
因此，首先我们要做的是计算 当前阵列的中点。
好了，我们会说我们是，第一 总之，寻找值19。
我们正试图找到19号。
这样做的第一个元素 阵列位于指数为零，
并在此最后一个元素 阵列位于指数14。
因此，我们会打电话给那些开始和结束。
>> 因此，我们计算出中点按 加0加上14除以2;
非常简单的中点。
我们可以说， 中点是现在7。
所以是15，我们在找什么？
不，这不对。
我们正在寻找19。
但我们知道，19大 比我们发现在中间。
>> 所以我们所能做的就是 更改起点
是刚刚的权 中点，并再次重复上述过程。
而当我们这样做，我们现在说的 新的起点就是数组位置8。
我们已经有效地完成工作是 无视一切的15次左右。
我们已经消除了一半 这个问题，现在，
而不必搜索 在我们的数组超过15元，
我们只需要搜索超过7。
因此，8是新的起点。
图14是仍然终点。
>> 而现在，我们过这一次。
我们计算出新的中点。
8加14是22，2是11分。
这是我们在寻找什么？
不，这不对。
我们正在寻找一个值的 不是我们刚刚发现少了。
所以，我们要重复 再次的过程。
我们要改变终点 只是为了中点的左侧。
因此，新的终点变成10。
而现在，这是唯一的一部分 数组我们必须通过排序。
所以，我们现在已经淘汰 12的15元素。
我们知道，如果19 存在阵列中，它
必须存在的元素之间的某处 号8和元件数目10。
>> 因此，我们再次计算新的中点。
8加10是18，2是9分。
在这种情况下，一看， 目标是在中间。
我们发现我们在寻找什么。
我们可以停止。
我们成功完成 二进制搜索。
好吧。
因此，我们知道这个算法 工作如果目标是
某处阵列的内部。
请问这种算法的工作，如果 目标不是阵列中？
好了，让我们开始这 再次，这一次，
让我们来看看该元素 16，这在视觉上可以看到
不会在阵列中任何地方存在。
>> 再次开始点是0。
再次终点是14。
这些是第一个的索引和 整个阵列的最后一个元素。
而我们将要经历的过程，我们只 经历了一遍，试图找到16，
尽管在视觉上，我们已经可以 告诉大家，它不会在那里。
我们只是想确保这个算法 将，实际上，仍然工作在某些方面
而不是只留给我们 陷入无限循环。
>> 那么，有什么步骤第一？
计算中点 目前阵。
什么是中点 目前阵？
嗯，这是7，对不对？
14加0除以2是7。
15，我们在寻找什么？
第
这是相当接近，但我们正在寻找 为一个值比稍大。
>> 因此，我们知道，这将 无处15的左侧。
目标是大于 什么是在中点。
因此，我们设定了新的起点 只是到中间的右边。
中点目前是7，所以 让我们说，新的起点为8。
而我们有效地已经 再行被忽略
该阵列的整个左半部。
>> 现在，我们重复 处理一次。
计算新的中点。
8加14是22，2是11分。
23，我们在寻找什么？
很不幸的是，不行。
我们正在寻找一个值 小于23。
所以在这种情况下，我们将 改变结束点是公正
到当前中点的左侧。
当前中点为11，并且 因此，我们将设置新的终点
下一次我们去 通过这一过程，以10。
>> 同样，我们再次经历的过程。
计算的中点。
8加10除以2是9。
19，我们在寻找什么？
很不幸的是，不行。
我们还在寻找 若干少于。
所以我们这次改变终点 是公正的中点的左侧。
中点目前是9， 因此终点将是8。
而现在，我们只是在寻找 在一个单一的元件阵列。
>> 这是什么阵的中点？
那么，它开始于8，它 结束于图8中，中点是8。
那是我们正在寻找什么？
我们寻找17？
不，我们正在寻找的16。
因此，如果它存在于数组中， 它必须存在的地方
到的，其中我们当前有左侧。
那么，我们该怎么办？
好了，我们将设置终点是公正 到当前中点的左侧。
因此，我们将终点更改为7。
你看一下刚才 这里发生了，有关系吗？
查一查这里。
>> 开始是现在大于结束。
有效地，两端 我们的阵列已经越过，
与开始点是 现在后的终点。
好了，不 任何意义，不是吗？
所以，现在，我们可以说的是，我们 有大小为0的子阵列。
而一旦我们得到了以 这一点，我们现在可以
保证元件16 在阵列中不存在，
因为起点 和终点越过。
所以它的不存在。
现在，请注意，这是略微 比开始点和结束不同
点是相同的。
如果我们一直在寻找 为17，这将有
过阵列，并且起始点在 并结束了最后一次迭代点
这些交叉点之前， 我们会发现17在那里。
只有当他们越过我们可以 保证元件不
存在阵列中。
>> 因此，让我们少了很多 步骤不是线性搜索。
在最坏的情况下，我们有 分裂n个元素的列表
多次在半找到目标， 要么是因为目标元素
将在最后的某处 师，或不存在，在所有。
因此，在最坏的情况下，我们不得不 分裂的array--你知道吗？
n次记录;我们 不得不削减问题
在半一定的次数。
这个次数是日志ñ。
>> 什么是最好的情况？
好了，我们第一次 计算的中点，
我们发现，我们所要寻找的。
在所有前面的 二进制搜索示例
我们刚刚走了过来，如果我们有 一直在寻找的元素15，
我们会立即发现。
这是在开始。
这是中点 在一个分裂的第一次尝试
在二进制搜索一个部门。
>> 因此在最坏的 情况下，二进制搜索运行
在日志n，这个基本上更好 比线性搜索，在最坏的情况下。
在最好的情况下，二进制 搜索运行在1欧米加。
所以二进制搜索是一个很大 比线性寻找更好的，
但你必须处理的过程 之前，你可以先整理你的数组
利用二分搜索的功率。
>> 我是道格·劳埃德。
这是CS 50。