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