[音乐播放] 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。