微信活动报名小程序_基于JavaScript完成的折半查找

基于JavaScript实现的折半查找算法示例       这篇文章主要介绍了基于JavaScript实现的折半查找算法,结合实例形式分析了折半查找的原理、操作步骤及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 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 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程序设计有所帮助。


内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://jzabcd.cn/ganhuo/3304.html