[音乐播放] 

ZAMYLA陈：首先，你可能会 通知有关的发现是，我们已经 已编写的代码我们。 这就是所谓的分配的代码。 所以，我们不只是编写我们自己的 从头开始编写代码了。 相反，我们正在填补空隙 在某些预先存在的代码。 

该find.c程序会提示输入数字 填补了草垛，搜索 在haystack一个用户提交的针， 它是通过调用排序和 定义的搜索，函数 在helpers.c。 所以find.c已经写入。 你的任务是写佣工。 

所以我们在做什么？ 我们正在实施两种功能。 搜索，返回true，如果一个值 在草垛被发现，返回 假如果该值 不是在干草堆。 然后我们也实施排序 这所谓的排序值数组。 

因此，让我们来解决搜索。 搜索当前实现为 线性搜索，但你可以做很多 比这更好。 线性搜索，现为O实现 n个时间，这是相当缓慢的。 虽然，它可以搜索 给它的任何列表。 你的任务是实现二分查找， 已运行日志的n时间为O。 这是相当快的。 

但是有一个规定。 二进制搜索只能搜索 通过预排序的列表。 这是为什么？ 

那么让我们来看一个例子。 给定的值的数组，草垛， 我们要去寻找 了针。 并且在该示例中， 整数3。 二进制搜索的工作方式是， 我们比较的中间值 阵列到针，很像如何 我们开了一个电话簿中间 在零一周页面。 

所以中间值相比较之后 针，你可以放弃任 左或阵列的右半 收紧你的界限。 在这种情况下，由于3，我们的针， 小于10，中间值，该 右边界会降低。 但尽量让你的界限 尽可能紧。 如果中间值不是针 那么你知道，你并不需要 它包含在你的搜索。 所以，你是对的绑定可以收紧 搜索范围更多的只是一点点， 等等等等，直到 你发现你的针。 

那么什么是伪代码是什么样子？ 好了，而我们仍然在寻找通过 列表中，仍然有元素 看在，我们把列表的中间， 而且中间值比较 我们的针。 如果他们是平等的，那么这意味着我们已经 发现了针，我们可以 返回true。 

否则，如果针小于 的中间值，那么这意味着我们 可以丢弃的右半边，只是 搜索数组的左侧。 否则，我们将搜索 右侧的数组。 并在结束时，如果你没有任何 留下来搜索更多的元素，但你 有没有发现你的针还没有，那么你 返回false，因为针 绝对不是在草堆。 

现在，一个整洁的事关于这个伪代码 在二分搜索的是，它可以是 解释为一种迭代 或递归实现。 因此，这将是递归的，如果你叫 在搜索中的搜索功能 功能上无论是数组的一半。 在一个稍后我们将介绍递归 当然，但知道它是一个 如果你想尝试的选择。 

现在，让我们来看看排序。 排序需要一个数组和整数 n，它是该数组的大小。 现在有各种不同类型的 不爽，你可以看一些 短裤的演示和讲解。 返回类型我们 排序功能是无效的。 这样就意味着我们不会 从排序返回任何数组。 我们究竟要改很 被传递到我们的数组。 

那是可能的，因为数组是 通过在C引用传递现在，我们将 看到后面会详细讲解，但 通过本质区别 在像整数和传球 在一个数组中，就是当你 传递一个整数，C只是要 使该整数的副本，并通过 它的功能。 原来的变量不会被改变 一旦该功能被完成。 与阵列，在另一方面，它的 不会让一个副本，你会 其实是可以编辑的 很数组本身。 

所以，一种类型的排序是 选择排序。 选择排序的工作原理是在开始 开始的时候，然后你遍历 在找到的最小元素。 然后你换了最小 元件与所述第一1。 然后移动到第二个元素 ，找到下一个最小的 元素，然后交换与该 阵列中的第二个因素，因为 第一个元素已经排序。 所以，你继续为每 在确定的最小元素 价值和交换出来。 

对于我等于0，第一个元素 到n减1，你要比较 之后，每一个未来的价值，并找到 最小值的索引。 一旦你找到的最小值指数， 您可以交换数组的值 最小和数组一 

另一种类型的排序，你可以 落实是冒泡排序。 因此，冒泡排序遍历列表 比较相邻元素和 交换的元素 是在错误的顺序。 并且以此方式，最大元件 将泡沫到底。 和列表进行排序，一旦没有更多的 元素已经被调换。 

因此，这些都是样的两个例子 您可以为实现算法 find程序。 一旦您完成排序，而你 做搜索，你就完蛋了。 我的名字是Zamyla，这是CS50。 

[音乐播放]