本篇文章为大家展示了怎么在JavaScript中实现折半查找算法,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。
一、问题描述:
在一个升序数组中,使用折半查找得到要查询的值的索引位置。如:
var a=[1,2,3,4,5,6,7,8,9]; search(a,3);//返回2 search(a,1);//左边界,返回0 search(a,9);//右边界,返回8 search(a,0);//比最小的值还小,返回"您查找的数值不存在" search(a,10);//比大的值还大,返回"您查找的数值不存在"
注:折半查找必须在有序数组中才有效,无序的数组不能实现查找功能。比如:在[10,5,6,7,8,9,20]
中查找10,中间索引位置的值为7,比较得出7比10小,因而应该在右子数组中查找,实际上不可能找到10;
二、我的实现
function search(arr,num) { var l=arr.length; var left=0; var right=l-1; var center=Math.floor((left+right)/2); while(left<=l-1&&right>=0){ if (arr[center]==num) return center; if (left==right) return "您查找的数不存在"; if (arr[center]>num) { right=center-1; center=Math.floor((left+right)/2); }else if (arr[center]说明:
1、基本思路:
每次比较,如果数组中间索引位置的值比要查找的值大,就转而在数组中间位置之前的子数组中查找;相反,如果数组中间索引位置的值比要查找的值大,就转而在数组中间位置之后的子数组中查找;如果数组中间索引位置的值恰好等于要查找的值,就返回该索引位置。
2、left定义查找范围的起始位置,right定义查找范围的结束位置,center定义查找范围的中间位置。
3、while中的逻辑说明:
(1)由于不知道具体查找查找多少次,while是比较好的选择;
(2)循环结束条件:
a、一旦当right小于0时,就不再查找,再纠缠也不会有结果。例如:在
a=[1,2,3,4,5,6,7,8,9]
中查找0,当查找范围变为left=0
,right=0
,center=0
时,进入while语句,由于arr[center]>0
,故执行right=center-1; center=Math.floor((left+right)/2);得到
right=-1
此时应不再进入循环;b、一旦当
left>l-1
时,就不再查找,同样再纠缠也不会有结果。例如:在a=[1,2,3,4,5,6,7,8,9]
中查找10,当查找范围变为left=8
,right=8
,center=8
时,进入while语句,由于arr[center]<10
,故执行left=center; center=Math.floor((left+right)/2);得到
left=9
,此时应不再进入循环;4、始终是通过center匹配到要查找的值;
5、
Math.floor
处理了查找范围长度为偶数的情况;6、当
left==right
了,而arr[center]==num
却没执行,可以得出结论查找不到的;7、当
arr[center]==num
时,整个函数都结束了,后面语句是不会执行的。上述内容就是怎么在JavaScript中实现折半查找算法,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注创新互联行业资讯频道。
分享标题:怎么在JavaScript中实现折半查找算法-创新互联
文章URL:http://bjjierui.cn/article/dgjpoe.html