欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

基于JavaScript实现的折半查找算法示例

程序员文章站 2024-01-23 19:48:16
本文实例讲述了基于javascript实现的折半查找算法。分享给大家供大家参考,具体如下: 折半查找也叫做二分查找,是针对有序表的一种查找方式,其思想如下: 将数组的第...

本文实例讲述了基于javascript实现的折半查找算法。分享给大家供大家参考,具体如下:

折半查找也叫做二分查找,是针对有序表的一种查找方式,其思想如下:

将数组的第一个位置设为下边界;

将数组的最后一个位置设为上边界;

如果下边界等于或小于上边界,则做如下操作:

   将中点设置为上边界加下边界之和除以二;
   如果中点的元素小于查询的值,则将下边界设置为中点元素所在下标加1;
   如果中点的元素大于查询的值,则将上边界设置为中点元素所在下标减1;
   否则中点元素即为要查找的元素,可以进行返回。

折半查找代码如下:

function binsearch(arr,data){//折半查找,也叫二分查找
    var upperbound=arr.length-1;
    var lowerbound=0;
    while(lowerbound<=upperbound){//未遍历完
      var mid=math.floor((lowerbound+upperbound)/2);
      document.write("当前中点为:"+mid+'<br>');//记录选中的中点
      if(arr[mid]<data){
        lowerbound=mid+1;
      }else if(arr[mid]>data){
        upperbound=mid-1;
      }else{
        return mid;
      }
    }
    return -1;
}

那么出现了重复的,我们需要计数。计数的思想就是在找到点的位置左右开始遍历,找到相同的则计数,找到不同的则停止遍历,代码如下:

function count(arr,data){//计算重复出现的次数
    var count=0;
    var position=binsearch(arr,data);//找出值所在位置
    if(position>-1){
      count++;//找到后,往左右一次遍历直到找到不同值后break
      for(var i=position-1;i>0;i--){
        if(arr[i]==data){
          count++;
        }else{
          break;
        }
      }
      for(var i=position+1;i<arr.length;i++){
        if(arr[i]==data){
          count++;
        }else{
          break;
        }
      }
    }
    return count;
}

最后是实验:

//实验
var nums=[1,2,2,3,3,4,5,6,7,8,9,10,11];
var bool=binsearch(nums,3);
document.write("所在位置为:"+bool+"<br>");
document.write("含有个数为:"+count(nums,3));
//当前中点为:6
//当前中点为:2
//当前中点为:4
//所在位置为:4
//当前中点为:6
//当前中点为:2
//当前中点为:4
//含有个数为:2

完整代码:

<!doctype html>
<html>
  <head>
    <meta charset="utf-8">
    <title>javascript折半查找</title>
  </head>
  <body>
<script type="text/javascript">
  function binsearch(arr,data){//折半查找,也叫二分查找
    var upperbound=arr.length-1;
    var lowerbound=0;
    while(lowerbound<=upperbound){//未遍历完
      var mid=math.floor((lowerbound+upperbound)/2);
      document.write("当前中点为:"+mid+'<br>');//记录选中的中点
      if(arr[mid]<data){
        lowerbound=mid+1;
      }else if(arr[mid]>data){
        upperbound=mid-1;
      }else{
        return mid;
      }
    }
    return -1;
  }
  function count(arr,data){//计算重复出现的次数
    var count=0;
    var position=binsearch(arr,data);//找出值所在位置
    if(position>-1){
      count++;//找到后,往左右一次遍历直到找到不同值后break
      for(var i=position-1;i>0;i--){
        if(arr[i]==data){
          count++;
        }else{
          break;
        }
      }
      for(var i=position+1;i<arr.length;i++){
        if(arr[i]==data){
          count++;
        }else{
          break;
        }
      }
    }
    return count;
  }
  //实验
  var nums=[1,2,2,3,3,4,5,6,7,8,9,10,11];
  var bool=binsearch(nums,3);
  document.write("所在位置为:"+bool+"<br>");
  document.write("含有个数为:"+count(nums,3));
  //当前中点为:6
  //当前中点为:2
  //当前中点为:4
  //所在位置为:4
  //当前中点为:6
  //当前中点为:2
  //当前中点为:4
  //含有个数为:2
</script>
  </body>
</html>

运行效果图如下:

基于JavaScript实现的折半查找算法示例

更多关于javascript相关内容感兴趣的读者可查看本站专题:《javascript数据结构与算法技巧总结》、《javascript数学运算用法总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结

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