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]<num) {
      left=center+1;
      center=Math.floor((left+right)/2);
    }
  }
}
var a=[1,2,3,4,5,6,7,8,9];
console.log(search(a,-2));

说明:

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时,整个函数都结束了,后面语句是不会执行的。

上述代码使用在线HTML/CSS/JavaScript代码运行工具http://tools.haodaima.com/code/HtmlJsRun测试运行结果如下:

希望本文所述对大家JavaScript程序设计有所帮助。

本文JavaScript折半查找(二分查找)算法原理与实现方法示例到此结束。不幸的人才,要更坚强。小编再次感谢大家对我们的支持!

您可能有感兴趣的文章
javascript请求servlet实现ajax示例(分享)

JavaScript操作表单_动力节点Java学院整理

纯javascript的ajax实现php异步提交表单的简单实例

JavaScript实现Ajax总结

初步了解JavaScript,Ajax,jQuery,并比较三者关系