怎么在JavaScript中实现折半查找算法-创新互联
本篇文章为大家展示了怎么在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://6mz.cn/article/dgjpoe.html