Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [线性搜索]
[帕特里克·施密德,哈佛大学]
这是CS50。[CS50.TV]
搜索的东西,你可能会做更多的时候比你想象的。
显然,每次你打开一个网页浏览器
和搜索的网页 -
或搜索您最喜爱的社交网站上的朋友 -
你正在寻找。
但是,这只是一小部分的搜索,你每天。
当你想在衣柜里发现一个蓝色的衬衫,
或者说完美的红衬衫的场合,
你正在寻找。
当你去一个商店,你从来没有去过之前,
你正在寻找的西兰花生产过道
你正在寻找。
你可能已经开始注意到
是根据你要找的
或如何被组织的项目,当你看到他们
它有一个影响您搜索。
例如,如果你的衬衫挂在衣橱里,
你也许可以随便挑出来没有太多的搜索。
如果你认为自己必须走在过道
西兰花,你可能要看看所有其他蔬菜
之前,你会发现西兰花。
线性搜索的是一个这样的搜索方法 - 或算法的一个例子。
正如它的名字所暗示的,
此方法搜索中的项,以线性方式,一前一后。
所以,当你正在寻找您最喜爱的搜索引擎的结果
你读下来的结果列表,
您使用的是线性搜索。
好吧。让我们来看一个例子。
假设我们有一个数字列表 - 2,4,0,5,3,7,8,和1 -
我们正在寻找数0。
很明显,你可以看到,0是排在第三位。
但是,一个计算机程序是不那么幸运。
它只能“看见”一个数的时间。
所以,在列表的开头开始,
它只能“看见”2。
然后程序检查 - 2等于0?
显然不是。所以,到下一个数字,4。
4等于0吗?不。
下一个,0。 “啊!零是等于0。
在那里,我们拥有它!这是排在第三位。
好吧。让我们来看看在一些伪代码。
这只是一对夫妇的线长,但让我们来看看它在一个时间线。
首先,让我们定义的功能 - 我们把它称为线性搜索 -
,它需要两个参数 - 键和阵列。
最关键的是,我们正在寻找的价值,
因此,在前面的例子中,这是零。
数组是一个数字列表
有,我们要寻找的所有的值。
所以,我们想要做的是,我们想看看 -
所有职位,所以从一开始的数组
直到非常数组末尾的 - 这样的数组的长度 -
在每一个位置上,并检查每一个。
所以,这是什么“为”循环做。
在每个位置上,我们说
“那是在平等的关键,我们正在寻找的,目前的位置吗?”
- 在前面的例子再次,关键是0 -
所以我们说:“是我等于零数组中的位置吗?”
如果是的话,我们将要返回的“i”,因为这是我们在当前位置。
所以,在前面的例子中,
这是第三的位置。
如果我们已经经历了整个阵列
我们并没有发现任何东西 -
让我们说,我们正在寻找数500
这显然不是在这个例子中 -
我们要返回的东西,
我们将返回-1。
我们只是返回-1,因为这是一个位置
数组中不存在。
因此,这意味着当你得到它从功能
它说:“嗯,好吧,我想我没有发现任何东西。
因此,500从来没有在那里。“
关于线性搜索是很好的事情,
它会在任何的物品清单,
无论项目的方式排序。
不要紧,西兰花是在农产品过道。
只要你走在过道从开始到结束,
你一定会找到它,
假设店没有用完的西兰花,当然。
但它的最大的优点也是它的最大弱点。
假设你有一个清单200号
排序从1到200。
如果你正在寻找数198,
你必须寻找几乎所有的数字列表
在你找到一个你要找的。
必须有一个更好的办法!
放心吧,有。
但是,这是一个主题为另一种视频。
另外,不要烦恼!
因为线性搜索是不是最好的解决方案,在所有情况下,
但这并不意味着,它并没有派上用场。
否则,你会发现,西兰花生产过道?
我的名字是帕特里克·施密德,这是CS50。
[CS50.TV]