品易云推流 关闭
文章详情页
文章 > JavaScript > javascript搜索算法有哪些

javascript搜索算法有哪些

头像

小妮浅浅

2021-06-05 11:13:21873浏览 · 0收藏 · 0评论

1、二分搜索

当一个集合被排序时,我们可以检查我们的检索值和中间项目,并将我们想要的一半丢弃。事实上,我们的目标可以在对数时间和恒定空间中找到。

this.binarySerach= function(item){
this.quickSort(); //排序
 
var low= 0,
 
high= array.length-1,
 
mid,
 
element;
 
while( low<=high){
mid= Math.floor( (low+high)/2 );
 
element= array[mid];
 
if( element<item ){
low= mid+1;
 
} else if( element>item){
high= mid-1;
 
} else {
return mid;
 
}
 
}
 
return -1;
 
};

2、二叉搜索树

另外一个排序集合的方法是生成一个二叉搜索树(BST)。对于BST的搜索效率和二分搜索一样高。用类似的方法,我们可以在每一次迭代中丢弃一半,我们知道不包含期望值的部分。实际上,另一个对集合进行排序的方法是按顺序对树木进行深度优先!

BST的创建发生在线时间和空间,但搜索需要一定的时间和空间。

为了验证二叉树是否为BST,我们可以递归检查每一个左子项是否总小于根(最大可能),每一个右子项总大于每一个根(最小可能)。需要线性时间和一定的空间。

以上就是javascript搜索算法的两种类型,希望对大家有所帮助。更多Javascript学习指路:Javascript

关注

关注公众号,随时随地在线学习

本教程部分素材来源于网络,版权问题联系站长!

底部广告图