欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

基于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è)為上邊界;

如果下邊界等于或小于上邊界,則做如下操作:

   將中點設(shè)置為上邊界加下邊界之和除以二;
   如果中點的元素小于查詢的值,則將下邊界設(shè)置為中點元素所在下標加1;
   如果中點的元素大于查詢的值,則將上邊界設(shè)置為中點元素所在下標減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;
}

那么出現(xiàn)了重復(fù)的,我們需要計數(shù)。計數(shù)的思想就是在找到點的位置左右開始遍歷,找到相同的則計數(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));
//當前中點為:6
//當前中點為:2
//當前中點為:4
//所在位置為:4
//當前中點為:6
//當前中點為:2
//當前中點為: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("當前中點為:"+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){//計算重復(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));
  //當前中點為:6
  //當前中點為:2
  //當前中點為:4
  //所在位置為:4
  //當前中點為:6
  //當前中點為:2
  //當前中點為:4
  //含有個數(shù)為:2
</script>
  </body>
</html>

運行效果圖如下:

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)

希望本文所述對大家JavaScript程序設(shè)計有所幫助。

相關(guān)文章

最新評論