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

网络编程 2024/11/17 佚名

3 1 2

本文实例讲述了基于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,折半查找,算法

华山资源网 Design By www.eoogi.com

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

华山资源网 Design By www.eoogi.com

评论“基于JavaScript实现的折半查找算法示例”

暂无评论...

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒经典版》的玩家都可以获得奖励。

更新日志

2024年11月17日

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

基于JavaScript实现的插入排序算法分析

AngularJS之自定义服务详解(factory、service、provider)

评论“基于JavaScript实现的折半查找算法示例”

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

更新日志

友情链接