溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
使用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完整代碼：
<!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>運行效果圖如下：
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
