折半查找也叫做二分查找，是针对有序表的一种查找方式，其思想如下：
将数组的第一个位置设为下边界；
将数组的最后一个位置设为上边界；
如果下边界等于或小于上边界，则做如下操作：
将中点设置为上边界加下边界之和除以二；
如果中点的元素小于查询的值，则将下边界设置为中点元素所在下标加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错误与调试技巧总结》