第九章 搜索算法
9.1 顺序搜索
????????顺序或线性搜索是最基本的搜索算法。它的机制是,将每一个数据结构中的元素和我们要找
的元素做比较。顺序搜索是最低效的一种搜索算法。
????????以下是其实现:
Array.prototype.sequentialSearch = function(item){
for(var i=0;i<this.length;i++){
if(item === this[i])
return i
}
return -1
}
????????顺序搜索迭代整个数组,并将每个数组元素和搜索项作比较。如果搜索到了,算法将用返回值来标示搜索成功。返回值可以是该搜索项本身,或是true,又或是搜索项的索引。如果没有找到该项,则返回-1,表示该索引不存在;也可以考虑返回false或者null。
????????假定有数组[5, 4, 3, 2, 1]和待搜索值3,下图展示了顺序搜索的示意图:
9.2 二分搜索
????????二分搜索算法的原理和猜数字游戏类似,就是那个有人说“我正想着一个1到100的数字”的
游戏。我们每回应一个数字,那个人就会说这个数字是高了、低了还是对了。
这个算法要求被搜索的数据结构已排序。以下是该算法遵循的步骤。
(1) 选择数组的中间值。
(2) 如果选中值是待搜索值,那么算法执行完毕(值找到了)。
(3) 如果待搜索值比选中值要小,则返回步骤1并在选中值左边的子数组中寻找。
(4) 如果待搜索值比选中值要大,则返回步骤1并在选种值右边的子数组中寻找。
Array.prototype.binarySearch = function(item){
this.sort()
var low=0,
high = this.length-1,
mid,element
while(low<=high){
mid = Math.floor((low+high)/2)
element = this[mid]
if(element<item){
low = mid+1
}else if(element>item){
high=mid-1
}else{
return mid
}
}
return -1
}
????????开始前需要先将数组排序,我们可以选择任何一个我们之前已经实现的排序算法。在数组排序之后,我们设置low和high指针(它们是边界)。
????????当low比high小时(行{4}),我们计算得到中间项索引并取得中间项的值,此处如果low比
high大,则意思是该待搜索值不存在并返回-1。接着,我们比较选中项的值和搜索值。如果小了,则选择数组低半边并重新开始。如果选中项的值比搜索值大了,则选择数组高半边并重新开始。若两者都是不是,则意味着选中项的值和搜索值相等,因此,直接返回该索引。
????????给定下图所示数组,让我们试试看搜索2。这些是算法将会执行的步骤:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!