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

2019-11-19 16:49:43

字体：大中小

来源：转载

供稿：网友

本文实例讲述了基于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>

运行效果图如下：