[Powered by Google Translate] [第3] [舒适] 内特 - 哈迪森] [哈佛大学] 这是CS50。[CS50.TV] 好吧,让我们开始吧。 欢迎CS50 4周。 如果你们打开Web浏览器和打开的pset 3, 争夺与CS50,我们要开始 通过的部分的问题存在。 就像上周,我们将工作在CS50空间, ,如果你也拉,以及, 如果你继续前进,请访问此链接,我已经起身在顶部。 现在是时候开始浏览网页。 我们有我们的小喜这里的程序。没有什么神秘的。 我想你们今天做的第一件事情就是去了几个解决方案 问题1,种示例解决方案, 只是,这样你可以得到什么样的代码的工作人员正在写一个感觉, 什么样的代码其他学生写作, 你看看它,因为我知道它的怪异 当您提交问题集的解决方案,并获得评论 你自己的版本,但有时它是有益的,看看其他人如何做, 尤其是很不错的期待。 在大多数情况下,我真的很感动,你们生产的解决方案。 我还没有开始看习题集2,但如果他们是什么第一, 这意味着什么,但好东西。 如果你看一下我的修改,让我们开始一路下跌,在第1次修订, 我们将采取一个快速的看看马里奥解决方案的。 如果你拉这件事,我们会提出这些程序是正确的。 有没有这些问题的正确性问题,而是 我们要谈一点点的不同的设计问题 被用在这里。 的事情,这是有趣的解决方案之一 是,它使用这个新的构造称为磅的定义, 有时也被称为作为一个哈希定义。 让我在这里放大。 A#定义允许您给这些数字在你的程序中。 在这种情况下,它的最大高度在Mario金字塔 为23,而不是把23在我的代码 我们将参照硬编码23 - 提供的名称,而不是MAX_HEIGHT这个数字, 所以,在这里我do-whil​​e循环 实际上,你可以参考MAX_HEIGHT 而不是把号码23英寸 [学生]:这样做的优点是什么? 这是一个很大的问题。 一个是可读性。 使用此#定义的优点是可读性。 当我读这段代码中,可以看到发生了什么事情。 我在这里可以看到,在这种情况下,我们正在测试 的高度,即<0,我们也可以定义 是最低限度的高度或最低高度。 另一个好处是,我可以读取行的其余部分 我们还在检查,以确保高度不大于最大高度, 因为我们要继续下去,而高度大于最大高度。 另一个好处是,如果我放大了一点点 如果我运行这个程序,我运行它,说,现在有23, 它会打印出23行一样,。 但说我想改变的最大高度, 现在我想限制的最大高度金字塔 只能说人,那是时髦的。 #包括,定义MAX_HEIGHT, 让我们说,我们要设置它等于10。 现在,在这一点上,所有我需要做的是改变它在这一个位置。 我可以重新编译代码,现在如果我尝试输入12, 它会提示我了。 在这种情况下,我们只用MAX_HEIGHT一次。 这并不是说大的麻烦去 并改变它在while循环中,如果你需要的话。 但是,在您在何处引用了相同的幻数的程序 一遍又一遍,这样的机制是非常方便的 因为你只需要改变一个时间的文件,它通常你把他们的顶端 和变化渗滤通过文件的其余部分。 其他的事情,我想指出,我认为在这个任务看起来真的很不错, 一个是变量的命名。 你在这里看到的,我们已经有了整数变量称为行,所谓的高度。 空间,哈希,它有助于使代码更具可读性一点, 多一点理解什么实际事情。 这是在对比使用,也就是说,随机字母 或只是官样文章完全。 最后记住一件事,我要指出的是,在for循环中, 通常这些迭代器变量,计数器,您在您的循环使用, 它的标准和传统的开始,我和那么j,则k 从那里,如果你需要更多的变数, 这仅仅是一个惯例。 有很多的公约。 这取决于你使用的编程语言。 但在C中,我们通常开始与我同在。 使用它没有意义,也就是说,a或b 视情况而定。 这是这一个。 如果你现在拉了第二次修订,你会看到一个马里奥, 而这一次是我们刚刚看到另一个类似, 但它确实挺酷的东西。 如果我们看一下在本节内内循环, 他们使用的是一些疯狂的寻找在此行中的语法在这里。 这就是所谓的三元运算符。 这是一个if else语句,凝结成一条线。 条件是这部分括号内。 这相当于说,如果j <高度 - 我 - 1。 然后的内容是什么,如果块的空间 然后将内容的else将#。 它本质上是一个空间分配给这个变量。 它把一个空间中的内容的块变量, 如果满足此条件,如果该条件没有被满足, 然后块变量得到#。 然后,当然,而不是建立整个字符串 印刷一切结束时,该解决方案把它打印出一个字符的时间。 很酷。 另外一对夫妇的事情来看待。我们将要讨论的贪婪。 现在,如果我们看贪婪,这第一个解决方案 使用#定义相当多的​​。 我们已经有了一个常量定义在这个程序的每一个不同的数字。 我们已经有了一个美分美元,一个季度,助攻,镍,和便士, 现在如果我们向下滚动和阅读代码, 我们可以看到一个标准的do-whil​​e循环打印了。 一种意识到这个问题的症结所在, 你需要转换的浮动,你在阅读的用户整数 准确地做数学题,这是因为 浮点数字,就像我们在演讲中简要地谈到, 这是不可能的,准确地反映每一个价值数行 因为有无穷多个值之间,并说,甚至3.1。 你可以有3.01和3.001及3.0001,你可以继续下去。 事实证明,用钱时,你的工作,你经常需要将其转换 转换为整数,所以你不会失去便士和诸如此类的东西。 这样做,和舍入是关键。 该解决方案使用了一个完全直接的,巨大的算法, 递减数剩余美分,第一季度, 然后通过硬币,然后由镍,然后通过便士, 和添加的硬币的数目,每次。 另一种解决方案,我们会看到,我缩小到4修订版, 有一个非常类似的开始,而是采用div和mod 在这里的数量来计算美分。 这样,宿舍的数量是等于除以25美分的数量, 这个工作的原因是因为我们正在做整数除法, 所以它丢弃任何剩余的。 [学生]:我们要不要发表评论,搜索吗? 这真的视情况而定。 [学生]:你注释以上代码就在这里。 是啊,所以有一堆不同的哲学。 我的个人哲学是你的代码是真正的真理, 喜欢你的代码是什么实际的计算机上执行, 所以你的代码应该尽可能地易读没有必要了许多意见。 这就是说,当你正在做的事情,是一种棘手的数学 或算法,这是很好的评论,这样就可以 谁是阅读你的代码中添加一个额外的维度,一个额外的层。 在这些解决方案中,他们往往更多地只是因为被注释掉 我们希望能够分发给才有人接他们时, 读他们很容易。 但可以肯定的是,我同意,这是沉重的。 [学生]:但是,当疑问,请重? 如果有疑问,去重了。 有时,有些人会说,返回0或类似的东西。 我认为这是一个荒谬的评论。 显然,这是发生了什么。 我不需要英语告诉我。 有时候人们会写的东西像“kthxbai!” 这是种可爱,但也未 这不是评论点或不之间的差异。 这些类型的评论是,哈哈哈。 酷。 在这一点上,让我们开始工作的习题集3节的问题。 如果你们拉起来了, 与上周一样,我们不打算在本节观看短裤。 我们将让你们这样做对你自己的时间和谈论的问题。 但是,现在在本节中,我们将要花费多一点的时间 谈论的编码基础 像我们一样上周,而不是,我们会更专注于 多一点点的理论,所以在谈论二进制搜索和排序。 你已经遵循了演讲, 有人可以给我一个概括的区别是什么 之间的二进制搜索和线性搜索? 这是怎么回事呢?当然。 线性搜索可通过在排序列表中的每一个元素 一个由一个一个逐个 二进制搜索将列表分为2组, 检查,如果你正在寻找的关键值,大于或小于中间值 你刚刚发现的,如果是小于,它会与下面的列表中 然后将再次做同样的功能 一路下来,直到它找到中点,等于本身的价值。 右。 我们为什么要关心? 我们为什么要谈论与线性搜索的二进制搜索? 是啊。 二进制是快了很多,所以如果你的问题的规模增加一倍 它需要一个步骤,而不是两倍多。 没错。 这是一个伟大的答案。 线性搜索是非常检查在一个时间,一个元件 正如我们所看到的第一天的演讲 当大卫•多姆德(David Drummond)通过他的手机,书中的例子 一次撕开了一个页的电话本 并不停地一遍又一遍,再这样做, 它要带他在电话簿中找到任何的很长一段时间, 除非,当然,他要找的人在一开始的字母。 在二进制搜索,你可以去快了很多, 它不只是两次以最快的速度或快3倍或4倍的速度。 但是,问题变得更小和更小的和更小的要快得多。 为了说明这一点,我们就开始谈论这是怎么回事 当我们写二进制搜索。 目前的问题是,如果我有一个数组的数字, 说,1,2,3,5,7,23,45,78,12323, 然后一吨的0后, 我们希望能够真的很快弄清楚什么是 这个数组。 我知道这似乎有点傻,有点做作, 因为现在它是。 我们有一个数组,没有很多的元素在里面, 如果我问你是否找出 23是在数组中,你能做到这一点很快 只是扫了一眼,告诉我“是”或“否”。 要考虑的是模拟想象一下,如果这个份上,说, 一个Excel电子表格有10000行,20000行。 当然,你可以执行命令F或控制F,看的东西了。 您还可以使用过滤器和搜索的东西, 但如果你有看通过该文件中的行由行线, 它会花费你很长的时间来找到它。 这是一种在电话簿的例子一样,太,其中 没有人期待通过一次的电话簿1页。 通常情况下,他们开到中间, 或在的情况下,大量的电话本和字典 你实际上它的第一个字母键, 你翻转,第一个字母,打开并开始经过那里。 再次提醒我你的名字。>>山姆。 山姆。 像Sam说,该线性搜索过程将是很慢的, ,而不是二进制搜索的工作方式是, 我们每次去通过我们的搜索算法的迭代, 我们要分一半的列表中,基本上, 成两个较小的列表。 然后在循环的下一次迭代,我们将其划分再 进入其他较小列表。 正如你可以看到,这个问题继续变得更小和更小的 因为我们保持每一次放弃一半的列表。 丢弃它是如何工作? 正如一个提醒,我们要做的,如果我们的电脑 和我们说,在此列表中,寻找5号 是,我们会选择一个中间的数字。 在此列表中,因为有1,2,3,4,5,6,7,8,9,10的号码, 我们会选择在第4位或第5位, 我们会打电话给我们的名单中。 选择在中间。 然后,就像山姆说,我们将测试一下,看看如果这个数字是相等的 的数量,我们希望得到我们想要的号码。 如果相等的话,我们已经找到了。我们赢了。 如果不相等,则有一对夫妇的情况下。 这两种情况是数数大于我们正在寻找, 或者是小于。 如果是更大的,我们移动到右边。 如果是,我们移动到左侧。 然后,我们再次重复整个过程, 右半或列表中的左半边。 在今天的部分的第一个问题是要弄清楚 实际上,我们可以在C代码中开始表达。 我们在这里得到的伪。 我们将开始做的是我拉了一个全新的空间, 保存本次修订,使我们有这些说明后, 我们将删除所有这一切,然后复制并粘贴问题集 此信息进入我们的空间,并希望这不会打破。 完美的。 如果你们都这样做,这段代码复制并粘贴到新的空间, 进入一个空白。 让我们尝试丹尼尔。如果你编译并运行这个程序,它的工作吗? 号>>什么是它在说什么? 它说,控制到达非void函数的结束。 是啊,所以我尝试运行它。 你们见过吗?你知道这意味着什么吗? 好吧,让我们来剖析这一点点。 它说在file.c在第9行,第1列,我们有一个错误,就像你说的, 它说,它源于错误警告和返回类型的警告。 它看起来喜欢的东西是怎么回事,这是有道理的返回类型。 我们有一个非void函数,这意味着我们已经有了一个功能 不返回void。 一个void函数,是一个看起来是这样的: 无效的foo(),它是无效的,因为返回类型为void, 这意味着,如果我们有一些东西在这里 如返回1,我们会得到一个编译错误。 但是,我们有一个非void函数。 在这种情况下,我们的非void函数是我们的搜索功能 因为它有一个返回布尔类型的。 当它的控制达到了一个非void函数, 这是因为搜索没有一个return语句。 它没有返回bool类型的任何东西。 我们可以解决这个问题,你们怎么想 搜索返回的默认? 搜索默认的返回值应该是什么? 因为这是我们可以放在最后。 夏洛特,你有什么? 真还是假的?>> TRUE或FALSE。 哪一个? 为False。我不知道。 假的?让我们试试吧。 为什么你会说,返回假的?这是伟大的直觉。 [夏洛特]我不知道。 我们将返回false,在这种情况下,因为这将是我们的默认 如果由于某种原因,该列表为空,或针 我们正在寻找不存在的。 然后在最后,如果我们不返回true早些时候在这个函数中, 我们一直知道,这个函数会说,不,这不是在数组中。 这不是在草堆里。 现在,如果我们要编译和运行它让我节省,所以我们可以把它拽上来。 现在,如果我们要编译和运行我们的程序,它的基础之上。 我们得到了我们的小提示。 如果我打了4架UH-OH。 它没有打印出任何东西。它看起来像一切结束行。 我们必须填写此英寸 我们谈到了该算法的伪代码一点点。 让我看看,保存, ,我会拉算法备份。 让我们来打这家伙。不。 在那里,它是。 如何才能做到这一点呢? 这将是一个很好的策略开始这段代码吗? 你必须选择一个中间的数字。 我们如何在一个数组中挑选一些呢? 有什么建议吗? [学生]:STRLEN除以2。 STRLEN除以2。这是一个伟大的。 strlen的作品特殊类型的数组。 什么类型的数组? String数组,字符数组。 这是同样的概念,我们要申请, 但我们不能使用strlen,因为我们没有一个字符数组。 我们有一个整型数组。 但到底是什么strlen的我们吗? 你知道它会为我们吗? [学生]:STRLEN让我们长。 没错,它使我们的长度。 STRLEN得到我们的数组的长度。 我们怎样才能在我们的二进制搜索程序? 你会得到一个数组的长度? [学生]:STRLEN? 你可以得到一个正确格式化C字符串数组的长度与strlen的。 ,不过,问题是,我们没有一个字符串数组。 如果我们回头看这段代码,我们有这样的整数数组。 我们怎么知道它有多长? [学生]:是否有一个相当于一个端点,如INT L或什么的? 事实证明,实际上不是,因此,在某种程度上,这是 这些事情,只是知道关于C之一, 有没有办法让一个数组的长度 如果我给你的是一个数组。 它的工作原理与字符串的原因,因为strlen的作品, 是因为如果一个字符串格式是否正确, 它会特别在最后的\ 0字符。 您也可以设想一下,如果你有一个格式不正确的字符串 有没有\ 0字符,那么整个事情并没有工作。 [学生]:你可以添加\ 0? 我们可以在这种情况下。 我们可以添加某种\ 0 或某种标志着字符,然后使用它。 但是,这不太去上班 因为\ 0是一个char类型, 在这里,我们有整数。 另一件事是,如果我们要使用一个特殊的值 像-1,以纪念数组末尾 然后,我们永远无法在我们的整数数组存储-1。 我们希望被卡住了。 事实证明,只有这样,才能得到长度 实际上是一个数组在C记得它 当你设置它,然后把它传递的阵列 所以,每当我有一个函数,会做一些工作 数组的整数或浮点数或双打,你有什么, 我还需要给函数的数组的长度, 这正是我们在这里所做的搜索功能。 如果你看一下,我们做了什么,当我们通过在我们的数组, 我们还通过在长度,尺寸。 这恰好是我们把这种现象称之为变量, 此参数或参数。 这就是所谓的一个函数的参数列表或参数列表, 这些也称为参数或参数。 人们在不同的时间使用不同的术语。 我有时会交换他们自己。 碰巧的是,这里被命名为这个变量同样 这定义在这里。 但他们不一样的东西。 资本化也很重要。 如果你看看这里发生的事情,我们声明 我们的int数组,这是我们所拨打的电话号码。 我们已经给我们的规模,这相当于我们的#定义在最顶端。 这将是8。 然后当我们再调用我们的搜索功能,下面, 我们通过我们要搜索​​的数量,我们已经提示, 从用户得到。 我们通过在阵列中,这个号码, 然后我们还必须通过在数组的大小, ,然后该值被存储大小为8 或传递给这个整数变量称为大小。 我们有阵列的大小。 现在,如果我们回到我们在谈论什么较早, 我觉得大小姐长大一点,我们需要做的是得到数组的长度 除以2,这将使我们的中点。 让我们来看看。 我有别人写这篇文章,并将其保存在自己的空间呢? 莱拉怎么样? 我能有你写这篇文章? 写的第一行,你把数组的长度,得到的中点 并将其存储在一个新的变量。 我给你几秒钟。你准备好了么? [学生听不清] 当然,我有你计算的中点 干草堆数组里面的搜索功能 用干草堆阵列的长度,这是变量的大小? 这里没有什么棘手的。 莱拉]大小/ 2和刚刚 并保存它,并点击“保存”按钮,在顶部上升, 我们会拉起来。 完美的。 我们走吧。真棒。 是,编译? [莱拉]没有,它需要的要高。 [内特]是啊,所以我们需要做什么? [莱拉,如int的中点或什么的。 真棒。是啊,让我们做到这一点,中点=大小。 编译? 让我们删除这条评论,并把它弄出来的方式。 究竟会不会编译这件事? 我们不会做任何事情的整数, 因此,我们需要打印或类似的东西。 是的,没错。 我们会得到一个未使用的变量。 还有什么工作呢? 我想你说了些什么,山姆。分号。 是的,我缺少的分号。 这将是一个常数事情的整个过程的术语。 我会做的最后一件事是,我把一些白色的空间,任何一方 运营商在这里,因为这通常是如何做到这一点 根据我们的风格指南。 我们有我们的数组的中点。 现在,如果我们还记得我们的算法, 第二步,我们不得不这样做,一旦我们有中点是什么? [学生]:如果它是大于[听不清]。 是啊,所以我们必须做一些比较,我们比较什么? 你说,如果它是大于。这是什么那句话指的是? 的数量,来了,如果这是大于中点,然后去到数组? 没错,这样的数字出现时,我们 针,所以我们比较针, 什么是我们比较针吗? 因为针是我们要寻找的是什么。 我们在比较得到的中点。 但它是有意义的检查,看看 如果针=的中点? 这是否有意义吗? 是否有人不同意吗? 让我们给它一个尝试,如果(针==中点)。 [学生]:printf的你发现了它。 [内特的printf(“我们发现了!\ n”); 否则,我要开始做不同的东西在这里。 我要开始把周围所有的时间if语句的大括号 只是因为,如果我们添加更多的东西,然后 我们没有得到的编译器。 是啊,山姆。你已经有了一个点。 的问题是,中点表示在数组中的位置, 但你可以得到它代表的价值在这个位置上的数组。 这是一个很好的点。 大家听到山姆说什么? 他说,中点是 只是在数组中的位置,但它不是实际的数组中的元素。 如果你写的代码现在想想, 如果我们看一下这里,在这个数组有8个元素在里面, 中点要在这个函数中的价值是什么? [学生]:4。 [内特] 4。 如果我们看一下数4 - ,我们可以运行此代码,在这里放一点点悲伤的脸 因为我们没有找到它,如果我们运行这个代码 是现在,上传,建筑,让我向下滚动, 如果我们看看数4, 我们发现了它,但我们没有得到这个输出是。 其中一个原因是,我们并没有返回true, 但当时我们真的找到4? 和Sam说“不”。 我们发现了什么? 我们真的找到了中点,如果我们看一下在阵列在这里, 这将是指数4,我们正在寻找的元素, 这是23。 我们如何真正得到该元素的中点 不只是中点本身吗? [学生]:我们将输入字符或什么的? 那么,具体怎么做,只是出于好奇吗? 你能否解释一下吗? 您的位置转换成数, 所以你不得不做出一定的联系,我认为这是char,但它可能不是。 是的,这是一个很好的点。 我们已经做了很多这种转换位置的字符,这些字符, 前两个问题集。 事实证明,在这里,这几乎是类似的 访问第i个字符在字符串中,如果是有道理的。 在这里,我们要访问的中点元素。 我们如何做到这一点? 凯文,你有什么建议,我们怎么可能做到这一点? 你可以做干草堆,开括号,中,右括号。 你可以写我们吗? 将它保存在这里,我们会拉,直至。 我们正在寻找在该行9, 我们意识到,我们不想比较针的中点, 但相反,我们要比较的针 位置中点我们的草垛阵列内的元素。 酷。 我们走吧。 是的,这看起来很不错,如果(针==草垛[中点])。 我们发现了它。 现在,如果我们运行的代码 - 我们将备份一点点, 编译,运行,现在如果我们看一下4, 我们没有找到它,因为现在我们实际上获得的23号。 我们现在要值23,这是我们比​​较我们的针。 但是,这是很好的。这是朝着正确的方向迈出的一步。 这就是我们想要做的。 我们并不试图对数组中的位置比较针 而是针对实际的数组中的元素。 如果我们现在再回头看我们的算法中的下一个步骤, 下一步是什么? 莱拉已经提到了简要介绍。 [学生]:检查,看它是否大于或小于,然后决定哪个方向移动。 [内特]是啊,所以我们会做什么? 你可以把一些 - 我本次修订, 然后,如果你把在一些线路,将这样做。 是啊,夏洛特。>>我有一个问题。 难道不应该的第一件事就是中点 - 1,因为 它的0索引,因此,如果我们把4,其实这不是我们要找的字符? 是的,和其他的问题,即- 这是一个伟大的渔获量,因为正在发生的事情可能发生 如果我们继续前进,我们永远不调整初始吗? 我猜我们可能最终做的是试图访问 在第8位的数组元素, 在这种情况下不存在。 我们会想要做某种会计的事实 我们有一些零的索引。 [夏洛特]对不起,我的意思是在方括号中的中点 - 1。 我们可以做到这一点。 我们将回到这个问题在短短位。 一旦我们开始得到了实际的循环, 那个时候,我们真的会看到这是发挥。 就目前而言,我们可以做到这一点,但你是完全正确的。 零索引将产生影响,我们需要考虑的。 让我们来看看。 如何大于和小于? [学生]:我要怎么弄了大于和小于部分。 我只是不知道,如果你发现这是不到的草垛中点或大于打印内容。 在这里,我可以节省难不倒我, [内特]是啊,如果你保存你有什么,我们就会把它。 我们走吧。 [学生]:我把问号是什么我不知道。 内特 - 这看上去很不错。 在这里,我们已经得到了问号,因为我们仍然不知道 我们要完全做到。 我们希望,做哎呀,我们已经得到了一些大括号对我们的所有时髦的。 我们会纠正这些大括号。 我们走吧。 还等什么,我们想要做的,按照我们的算法, 如果我们没有发现针? 的情况下,说针是小于我们正在寻找。凯文。 只有看的左半边。 对,所以我们会把在这里评论说:“看在左半边。” 如果针是大于干草堆的中点,我们要怎么办? [学生]:那你看右半边。 看右半边,“看右半边。” 不能太寒酸。 好了,所以在这一点上,东西都看起来相当不错。 写的代码的问题是什么? [学生]:您没有终点的一半。 是的,我们没有端点的一半。 此外,我们也只有通过这一次要去。 我们只是要在一个中点。 无论是元素是存在的,或者它不是。 为了完成这一目标,我们需要做某种形式的重复。 我们需要不断重复,直到我们找到 无论是元素,因为我们已经缩小,终于找到了, ,或者它不是在那里,因为我们已经看遍了所有的事情, 在适当半的阵列,发现在那里,没有什么是。 每当我们已经有了这样的重复,那我们该怎么使用? [学生]:一个循环。 某种形式的循环。是。 [学生]:我们可以做一个do-whil​​e循环,有它这样做,然后, 针不相等的,我不知道我要去哪里与。 但有点像做,只要它不等于的值,用户输入。 是啊,所以让我们来看看,这怎么可能写出来吗? 你说让我们使用一个do-whil​​e循环。 在什么地方开始? [学生]右后大小/ 2。 [内特]好吧,什么是我们该怎么办? 我们将填写后的一段时间。 什么是我们该怎么办? [学生]:你不是我们想要做的所有的东西,我们如果部分吗? [内特]做了这一切东西,太棒了。 复制和粘贴。 哦,男人。 让我们来看看,如果这个工程,如果我们能“选项卡这种过度。 美丽的。 好了,我们保存,这样你们。 所有权利,我们将做到这一点,而 而条件后是什么? [学生]:当针不相等的,所以像惊叹号。 但我不知道到底是什么还。 [内特]是啊,这是一个办法做到这一点。 山姆,你有意见吗? [三]我记得当我看着影片, 我的截图之一,像我们做的伪代码时, 最大值和最小值之间有一定的关系。 我认为这是类似的东西如果max是永远小于min。 明白了。 [三]想,如果最大不小于分钟或类似的东西, 因为这将意味着,您搜索过的一切。 是啊,所以它听起来像最大值和最小值是指? [三],整数的值,要改变 相对于我们把中点。 没错。 [三]在这一点上,它是怎么回事[听不清]计算的最大值和最小值。 中点这是最大和最小的想法。 这是否有意义人吗? 如果我们要开始找我们要如何做到这一点迭代, 你是完全正确的,我们要使用某种do-whil​​e循环。 但我想,如果我们还记得发生了什么事在这个数组当场 ,什么是实际发生的事情,我会写在这里 在第一次迭代的二进制搜索,我们有 我要使用b和e来表示开始。 我们的阵列,然后结束。 我们知道,开始的时候是在4对在这里, 我们知道,到底是在108。 说,我们正在寻找的15号。 当我们第一次这样做,就像我们前面看到的, 中点将是16或23 这取决于我们如何计算的事情了。 由于等分的中间,给我们这个空间 在16和23之间,我们不能整除它 或者将其与一个真正的中点。 我们将在16岁。 我们将实现“嘿,16> 15,我们正在寻找的。” 然后看阵列的左半边 我们最终会做什么是丢弃 这整个上部 并说:“好了,现在我们的终点会到这里来。” 我们的循环的下一个迭代的,我们现在看这个数组, 有效地舍弃这部分,因为现在 如果我们的中点的开始和结束之间的差异, 我们发现我们的中点为8, 然后,我们可以测试,看看它是关系到我们正在寻找数, 15日,有15个是更大的, 所以我们必须要移动到列表中的右边部分, 我们知道,因为我们是人类,我们可以看到它。 我们知道,右侧部分将是我们在那里找到它, 但电脑不知道这一点,所以我们要做的是,我们实际上 已经上去了,现在开始和结束 是相同的点的中点,所以成为在这一点上的列表中的唯一编号, 这是15日,我们已经找到了。 这是否透露了一些关于这整个的最大和最小的符号是怎么回事, 跟踪的端点的数组,以便找出 如何缩小东西下来? 如果这是不等于15,会发生什么? 如果我们一直在寻找,这个数字是15,而不是16吗? 我们会说,“哦,这是更大的。 我们要回去的左边。“ 我们将我们的电子的权利, 在这一点上,我们有一个端点,是相互矛盾的。 这不会是能够搜索到任何更多的元素 因为现在我们有我们的端点和我们的起点, 我们的最大和我们的分,现在翻转。 我们搜索整个阵列。我们无法找到任何东西。 这一点上,我们会说,“好了,我们要制止这种算法。 我们没有发现任何东西。我们知道这是不是在这里。“ 这是怎么回事呢? [学生]:电脑的开关究竟是如何结束了吗? 如何结束前开始吗? 结束前开始 因为,我们要做的每次我们这样做的数学。 我们交换的方式是,如果你的第一次,我们这样做交换 在那里我们有在4的开头和结尾 所有的方式,在108和我们的中点,也就是说,在16 - 我要重置回15,如果我们正在寻找的15个, 我们知道我们做了什么,当我们检查了16看到,这是更大的 想放弃整个右半部分的列表, 我们看到什么,我们想要做的是将这个电子就在这里。 实际上,电子转移到了之前的中点。 同样,当我们这样做的算法迭代 和中点是在8, 我们发现,8 <15,所以我们希望移动的b 过去的中点。 现在,始端和末端都在这15一起。 如果我们已经发生的事情,寻找一些其他的价值,而不是15, 如果这15而不是16, 我们会发现,E,我们要移动前的中点。 电子翻转少于B。 让我们通过我们实际上如何结束这种编码算法。 我们知道,我们希望有这样的中点计算。 我们也知道,我们要跟踪的开头和结尾的数组 我们目前的阵列,所以我们可以计算出 这个列表的左半和右半列表。 我们做到这一点的开始和结束, 或者我们可以给他们打电话的最小值和最大值。 我将使用开始和结束时间。 当我们开始之前,如果我们回头看,我们的例子中,在这里, 我们一开始就被设定为一开始的数组,是自然的。 什么样的指标是这样的吗?我们开始可以吗? 丹尼尔。 [丹尼尔]的干草堆[0]。 [内特]是啊,所以我们可以设置它等于干草堆[0]。 ,不过,问题是,这给我们的第一个元素的位置。 它给我们的第一个元素或实际值,第一个位置的索引。 [学生]:这将转换为0.20? 内特 - 这将是孔,它不会做任何的皈依。 它会做的,是将存储4开始, 那么这将是很难进行比较,对开始 因为BEGIN将持有的价值4, 这是我们的数组的开始, 但我们要跟踪的指数数组中的 相反的值。 实际上,我们将使用0,这样的。 对于最终的阵列夏洛特带来了这起得更早一点。 这是我们会考虑到零的索引。 夏洛特,什么是数组末尾的吗? 什么是指数结束? [夏洛特] - 1。 是啊,它的大小,我们应该使用? 我们应该使用资金规模或小写的大小? 资本的大小。 在这种情况下,我们可以利用资金规模。 如果我们希望这个函数是可移植的 在其他程序中使用此功能, 实际上,我们可以使用小写字母的大小。 这是一件好事。 但夏洛特是完全正确的,我们希望有大小 - 1。 在这点 [学生]:它是如何,你可以使用大写的大小吗? 它是如何,我们可以使用大写的大小吗? 事实证明,这些#定义是真的, 引擎盖下,一个文本,如查找和替换,如果是有道理的。 当你编译你的代码,预处理阶段 编译器通过文件, 它看起来无处不在,你写的资金规模, 它取代这些文字的字面与8,就这样。 从这个意义上说,这是非常不同的变量。 它不占用任何内存空间。 这是一个简单的文本替换技巧。 在这种情况下,我们将要使用的大小。 在这里,我们想这样做某种形式的重复, 我们在正确的轨道上,与我们的do-whil​​e循环。 我们想要做的事,直到条件不成立了, 正如我们前面所看到的,我们看到,该条件 的确,我们不希望最终 是小于的开始。 这是我们的停止条件。 如果发生这种情况,我们要停止,并宣布,“嘿,我们没有发现任何东西。” 为了表达这一点,我们要使用某种形式的循环。 在这种情况下,它是一个do-whil​​e循环,for循环,while循环? 在这里我们有一个do-whil​​e循环。 你们这样的方法吗? 你认为我们应该尝试不同的方法吗? 凯文,有什么想法吗? 我们可以有一个while循环,因为我们知道最大 将比开始不管怎么说分钟。 是啊,所以没有初始化,需要做的。 这些do-whil​​e循环是伟大的,当你要初始化的东西 在此之前的测试,而在这里 我们知道,我们不打算再继续重新初始化开始和结束 每一轮的循环。 我们知道,我们要对其进行初始化,然后检查我们的条件。 在这种情况下,实际上,我会用一个简单的while循环中去。 事实证明,do-whil​​e循环是相当不经常使用。 很多地方甚至不教不while循环。 他们是很好的处理用户输入,因此迄今为止我们已经看到了很多人。 但正常的,while循环,也有很多比较常见的。 事实证明,这种情况书面 不会真的对我们很有好处,这是为什么呢? 对不起,我不知道你的名字。 我杰里。>>对不起吗? 这是B-O-R-U-I。 哦,好吧。 我看不到你,我的名单上。 哦,这是因为,哦,这是有道理的。 你有一个想法,这个while循环的原因可能无法按预期, 写的条件吗? [杰里,你的意思是你想要的所有东西后,它的? 是啊,所以这是一个。 我们可能需要把所有的这些东西进入while循环,这是完全正确的。 其他的事情,不过,这是一个有点比较麻烦的是,这种情况不工作。 [学生]:您需要翻转。 对,所以这种情况将不会是真实的最初因为我们谈论的方式。 我们想要做的事,直到结束<开始, 但我们想要做的东西,而 开始≤年底。 还有,反转的逻辑。 我犯了这些错误的时间。 [学生]:为什么必须小于或等于? 因为你还记得的情况下,我们得到了 那里只有一个元素,我们比下降, 我们正在寻找在数组中的15? 我们的开始和结束都是一样的元素。 我们要确保我们处理这种情况。 如果我们做了一个直不到, 我们将只能得到2个元素的数组。 一旦我们得到了下来,最后一个元素,如果这是我们的元素,我们永远也找不到它。 现在,在这里,我们可以做的正是像你说的话。 我们可以开始扑通东西,到我们的while循环中。 我们可以扑通一声在我们的中点。 我们可以把所有这些if语句, 将它们拉出来的这do-whil​​e循环, 扑通一声, 干净的东西一点点, ,我会继续保存本次修订。 在这一点上,我们已经很接近了。 山姆。 我想你也必须有int中点,=大小 - 1/2。 明白了,大小 - 1/2。 我们需要改变该行的还有什么呢? 这是一个很好的渔获物。 大小做什么呢?我们不断变化的大小吗? 为了保持这样的线,我们要改变的大小。 我们每次去周围的循环,我们必须改变大小。 但是,请记住,当我们将通过我们的例子只是一点点, 我们开始在4 结束在108一路过来吗? 我们是如何计算的中点? 我们使用的大小? 我们使用的开始和结束,而不是吗? 它的结束和开始之间的差异。 没错,究竟如何,我应该写,夏洛特? 刚刚结束“ - ”开始“。 你不会需要做的 - 1 因为 - 1已包含在最终并已开始。 [内特]太好了,你是完全正确的。 我们没有做 - 1 - 1已被列入 并占当我们初始化结束变量。 还有什么我需要做的语法有这条线是有意义吗? [学生]:加开始。加上开始的呢? [学生]:在最后。 因为它只是计算一半的长度。 您需要添加的开始。 [内特]这算什么我们? 如果我们想结束这个循环迭代, 到底是怎么回事,是在第7的位置索引。 开始的位置为0。 请记住,我们正在寻找任何 位置3或4的位置。 如果我们看一下这道数学,只是为了使这一点更有形, 在这里把一些数字,我们有7,0, 7 - 0,然后/ 2 3整数除法,那是。 那么我们需要再添加回我们的开始吗? 在这种情况下,我们不。 在第一次迭代中,这将是罚款,因为BEGIN为0。 但是,我们的进步,我们真的只需要 结束 - 开始/ 2。 这里还有另外一个绝招,那就是即一个优先级。 [学生]:我们需要括号? [内特]没错,这是因为,如果我们不把这些括号, 那么这条线将被解释,而不是 (完) - (开始/ 2),这是我们绝对不希望。 对于那些优先级规则。 [学生]:为什么不是结束+开始的呢? 为什么它没有结束“+”开始“? [学生]:为什么不说? 为什么会+? 我想你是对的。 [学生]:因为它的平均? [内特]末开始,你是完全正确的。 哇,我完全弄错了。你说得对。 如果我们在做减,我们将要添加的开始。互动式 在这种情况下,你是非常正确的,我们要采取平均两个, 所以我们要加入他们,而不是减去它们。 [学生]:这也将工作,如果你真的结束 - 开始/ 2 +开始。 如果我们这样做,我相信。 例如,如果我们在开始时, 而我们这里转移, 15。 现在开始在位置2。 到底是在第7位。 如果我们减去它们,我们可以得到5。 除以2,得2。 然后,我们加2, 并因此获得第4的位置, 就在这里,这是中点。 [学生]:我们需要照顾的包装吗? 在何种意义上,我们需要照顾的包装吗? 如果总和或之间的区别 这取决于我们如何做到这一点是不是偶数。 然后,计算机会感到困惑是否当的2.5; 你移动到左边或有权决定的中点? 明白了。 事实证明,与整数除法, 我们永远不要让这些浮点数。 我们从来没有得到小数。 这是完全丢弃。 如果你有一台电脑分两个int变量, 一个是7,和另一个是2, 你不会得到3.5的结果。 它会得到3。 其余部分将被丢弃,所以它是有效的舍入 不是圆形,而是一个楼层,如果你们是熟悉的,在数学, 你完全放弃小数, 所以你基本上截断它下调至最接近的 整个位置,最接近的整数。 [学生]:但是,这是有问题的,因为如果你有7个元素的数组 然后,自动将第三个元素的中点,而不是第4。 我们该如​​何处理呢? 这是有问题的,因为如果我们有一个数组中的7, 它会选择,而不是第3第4。 你能解释一下吗? [学生]:因为如果你有7个元素,那么第4个元素 的中点,对不对? 零的索引,请记住您的评论。 [学生]:是的,所以在位置3。这将是中点。 是啊。 哦,好吧。我明白你的意思。 这是一种奇怪的,因为我们习惯了这整个概念 摆脱小数。 这是一个很好的点。 让我们来完成这件事。 我们计算过我们的中点。 我们正在测试,看看我们的针是等于中间值。 我们要打印,我们发现了它,但说真的,在这种情况下,我们想要做的是什么呢? 我们已经找到了,所以我们希望让来电者知道,我们发现它。 我们已经有了一个功能,是一个布尔类型的函数。 WE信号的方式向我们的函数的调用者,我们已经准备好 我们说:“嘿,这是真的。” 我们将如何做到这一点,凯文? 你点头你的头。>> [凯文]返回true。 [内特]没错,返回true。 现在,如果它是不相等的,怎么会看的左半边吗? 有什么想法? 斯特拉,任何想法? 您需要设置一个新的位置结束。 是啊。 所以,我们要做的中点位置 - 结束。 大。 我们需要建立一个新的位置结束 看的左半边。 这就是我们谈到了之前在那里 我要回这个例子。 我已经在这里开始,然后我结束所有来这里的路上。 同样,如果我们要找的15,我们的中点是在16, 我们认识到,“哎呀,16。 我们要移动到左边的一半。“ 然后,我们将移动到15月底, 我们这样做的一个距离的中点 并设置作为我们新的结束。 同样,如果我们想看看在适当的一半,如何将我们做到这一点呢? 你有一个想法? [学生]:您刚才设置开始的中点+ 1。 [内特大。 现在的情况,我们没有发现任何东西, 得到悉心照顾我们吗? 丹尼尔,这是否得到照顾我们吗? [丹尼尔]第 [内特]如果我们把整个数组,我们没有发现任何东西, ,照顾,我们还是应该照顾? [丹尼尔],而条件。 [内特]是啊,while条件,准确。 如果我们没有发现任何东西,它会照顾整个数组。 这个while循环将结束。 我们从来没有遇到过这种状况, 我们可以返回false。 我们也可以离开这一点,如果这样的在这里 因为如果这个说法是正确的, 和我们函数将返回, 因此,我们将基本上取消该功能,在这一点上 当我们返回true。 但这种结构会发生什么呢? 这项工作完全,或者是有一些逻辑上的缺陷在那里? 在那里有一些逻辑上的缺陷,它的设立的方式。 它可能是什么? [学生]:为什么你需要 - 和+ 1秒? 我们的阵列设置,是我们新的左半部和右半。 [学生]:但是,为什么你不能做到这一点不 - 1和+ 1秒? [内特]我们可以设置它等于中点? 有关,可能是什么问题? [学生]:我想这是低效的,因为你正在检查已检查的值的。 [内特]没错,所以山姆是完全正确的。 如果您设置的结束和开始的中点 - 1 + 1沉思, 在一些点在未来,我们将最终再次检查的中点。 [学生]:我开始在pset,然后我有类似的东西 我忘了+ 1,它被卡在一个无限循环。 是的,因为在某些时候,你永远不会得到的开始和结束 实际上是重叠的。 酷。 还有一个更合乎逻辑的缺陷,那就是,这绝对是 一个else if。 为什么会这样呢? 原因是如果它不是别的,如果你看到它,凯文? [凯文]是啊,因为你改变的终点。 [内特]没错。 我们正在改变端点, ,如果它写这样我们就会使空间之间的 它会检查这种情况。 这种情况下,如果成功,将中止的功能。 然后,它会检查这个情况下, 如果成功,将调整的终结点, ,然后它会继续检查这种情况。 但在这一点上,我们不希望它继续检查。 幸运的是,我们还没有复位的中点, 我们知道,这种情况下是不会得逞的。 但是,我们一定要在那里把其他 即使可能在这种情况下, 因为我们没有调整的中点,这区别吗? 没有,因为这些情况都是排斥的。 再次,是我不好。 我们不这样做,我想,否则,如果需要这个。 我们可以给它一个尝试,并运行它,并看看会发生什么。 大厦发生了错误。 这可能是因为我在这里这些B和E的。 我还有更多的人高达顶部? 它看起来并不像它。 我们要放大,建造, 就这样吧,所以现在如果我们搜索15, 是。 让我放大。 15,是的。我们可以再次运行它。 上载的源代码,构建,运行。 这样的事情,我们可以搜索13, 和我们没有得到任何打印出来的,所以它不是发现了这一点。 这是伟大的,因为它不是在我们的名单。 我们现在没有时间了。 这将是这个星期。 感谢您的加盟,看你以后。 [CS50.TV]