使用JavaScript實(shí)現(xiàn)一個(gè)折半查找算法

發(fā)布時(shí)間：2021-04-12 16:54:41 來(lái)源：億速云閱讀：228 作者：Leah 欄目：web開(kāi)發(fā)

使用JavaScript實(shí)現(xiàn)一個(gè)折半查找算法？很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來(lái)學(xué)習(xí)下，希望你能有所收獲。

折半查找代碼如下：

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ù)的，我們需要計(jì)數(shù)。計(jì)數(shù)的思想就是在找到點(diǎn)的位置左右開(kāi)始遍歷，找到相同的則計(jì)數(shù)，找到不同的則停止遍歷，代碼如下：

function count(arr,data){//計(jì)算重復(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;
}

最后是實(shí)驗(yàn)：

//實(shí)驗(yàn)
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("含有個(gè)數(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
//含有個(gè)數(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){//計(jì)算重復(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;
  }
  //實(shí)驗(yàn)
  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("含有個(gè)數(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
  //含有個(gè)數(shù)為：2
</script>
  </body>
</html>

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

使用JavaScript實(shí)現(xiàn)一個(gè)折半查找算法

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝您對(duì)億速云的支持。

向AI問(wèn)一下細(xì)節(jié)

使用JavaScript實(shí)現(xiàn)一個(gè)折半查找算法

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽