基于JavaScript實現(xiàn)的折半查找算法示例

更新時間：2017年04月14日 09:26:32 作者：布瑞澤的童話

這篇文章主要介紹了基于JavaScript實現(xiàn)的折半查找算法,結(jié)合實例形式分析了折半查找的原理、操作步驟及javascript實現(xiàn)折半查找的相關(guān)操作技巧與注意事項,需要的朋友可以參考下

本文實例講述了基于JavaScript實現(xiàn)的折半查找算法。分享給大家供大家參考，具體如下：

折半查找也叫做二分查找，是針對有序表的一種查找方式，其思想如下：

將數(shù)組的第一個位置設(shè)為下邊界；

將數(shù)組的最后一個位置設(shè)為上邊界；

如果下邊界等于或小于上邊界，則做如下操作：

   將中點(diǎn)設(shè)置為上邊界加下邊界之和除以二；
   如果中點(diǎn)的元素小于查詢的值，則將下邊界設(shè)置為中點(diǎn)元素所在下標(biāo)加1；
   如果中點(diǎn)的元素大于查詢的值，則將上邊界設(shè)置為中點(diǎn)元素所在下標(biāo)減1；
   否則中點(diǎn)元素即為要查找的元素，可以進(jìn)行返回。

折半查找代碼如下：

function binSearch(arr,data){//折半查找，也叫二分查找
    var upperBound=arr.length-1;
    var lowerBound=0;
    while(lowerBound<=upperBound){//未遍歷完
      var mid=Math.floor((lowerBound+upperBound)/2);
      document.write("當(dāng)前中點(diǎn)為："+mid+'<br>');//記錄選中的中點(diǎn)
      if(arr[mid]<data){
        lowerBound=mid+1;
      }else if(arr[mid]>data){
        upperBound=mid-1;
      }else{
        return mid;
      }
    }
    return -1;
}

那么出現(xiàn)了重復(fù)的，我們需要計數(shù)。計數(shù)的思想就是在找到點(diǎn)的位置左右開始遍歷，找到相同的則計數(shù)，找到不同的則停止遍歷，代碼如下：

function count(arr,data){//計算重復(fù)出現(xiàn)的次數(shù)
    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("含有個數(shù)為："+count(nums,3));
//當(dāng)前中點(diǎn)為：6
//當(dāng)前中點(diǎn)為：2
//當(dāng)前中點(diǎn)為：4
//所在位置為：4
//當(dāng)前中點(diǎn)為：6
//當(dāng)前中點(diǎn)為：2
//當(dāng)前中點(diǎn)為：4
//含有個數(shù)為：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("當(dāng)前中點(diǎn)為："+mid+'<br>');//記錄選中的中點(diǎn)
      if(arr[mid]<data){
        lowerBound=mid+1;
      }else if(arr[mid]>data){
        upperBound=mid-1;
      }else{
        return mid;
      }
    }
    return -1;
  }
  function count(arr,data){//計算重復(fù)出現(xiàn)的次數(shù)
    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("含有個數(shù)為："+count(nums,3));
  //當(dāng)前中點(diǎn)為：6
  //當(dāng)前中點(diǎn)為：2
  //當(dāng)前中點(diǎn)為：4
  //所在位置為：4
  //當(dāng)前中點(diǎn)為：6
  //當(dāng)前中點(diǎn)為：2
  //當(dāng)前中點(diǎn)為：4
  //含有個數(shù)為：2
</script>
  </body>
</html>

運(yùn)行效果圖如下：