基于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>

運行效果圖如下：