基于JavaScript實現(xià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)文章
JavaScript將數(shù)據(jù)轉(zhuǎn)換成整數(shù)的方法
這篇文章主要介紹了JavaScript將數(shù)據(jù)轉(zhuǎn)換成整數(shù)的方法,有需要的朋友可以參考一下2014-01-01javascript Xml增刪改查(IE下)操作實現(xiàn)代碼
比較不錯的實現(xiàn)代碼,大家可以仔細的看下,思路。2009-01-01JS解決?Array.fill()參數(shù)為對象指向同一個引用地址的問題
這篇文章主要介紹了JS解決?Array.fill()參數(shù)為對象指向同一個引用地址問題,解決方案使用map返回出不同的引用的地址,fill參數(shù)可隨意填寫(不為空),主要是map函數(shù)中返回的數(shù)據(jù),需要的朋友可以參考下2023-02-02使用JavaScript開發(fā)跨平臺的桌面應(yīng)用詳解
下面小編就為大家?guī)硪黄褂肑avaScript開發(fā)跨平臺的桌面應(yīng)用詳解。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-07-07使用ajax的post同步執(zhí)行(實現(xiàn)方法)
下面小編就為大家分享一篇使用ajax的post同步執(zhí)行(實現(xiàn)方法),具有很好的參考價值,希望對大家有所幫助2017-12-12JavaScript中關(guān)于iframe滾動條的去除和保留
在開發(fā)中經(jīng)常遇到去掉全部的滾動條,去掉右邊的滾動條且保留底下的滾動條,去掉底下的滾動條且保留右邊的滾動條,大家基于js是怎么實現(xiàn)的呢?下面小編通過本文給大家詳細介紹下,對js iframe滾動條相關(guān)知識感興趣的朋友一起學(xué)習吧2016-11-11