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