JavaScript折半查找与重复计数算法实现

作者：纸飞机时间：2026-10-22 03:07:04浏览：508

本文详细介绍基于JavaScript实现的折半查找（二分查找）算法，适用于有序数组。通过设定上下边界与中点比较来定位目标值。此外，文章扩展了查找相同值的计数逻辑，通过向左右两侧遍历统计重复元素个数，并附带完整代码与运行效果演示。

折半查找算法原理

本文通过具体实例展示如何使用JavaScript编写折半查找算法，供读者参考学习。

折半查找，亦称二分查找，是一种专门针对有序数据表的查找策略，其核心逻辑如下：

首先，将数组的起始索引定义为下边界；

其次，将数组的末尾索引定义为上边界；

当且仅当下边界索引小于或等于上边界索引时，执行以下查找步骤：

计算中点索引，即上边界与下边界之和除以2并向下取整；随后判断中点元素与目标值的关系：若中点元素小于目标值，则将下边界更新为中点索引加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编程实践提供有益帮助。

作者最新文章

JS动态构建复杂嵌套JSON对象的方法

2026-11-05 15:41:52

JS负数取余为什么是负数？详解余数与模运算区别

2026-11-05 13:34:41

JS 解压出现乱码或报错怎么解决？

2026-11-05 12:32:38

JS 中 startsWith、indexOf 与正则判断字符串前缀的对比

2026-11-04 22:19:43

JS解析Excel后怎么将数据转换为JSON格式

2026-11-04 20:58:28