JS二分查找算法詳解
更新時間：2017年11月01日 10:21:56 作者：模糊的星空
這篇文章主要為大家詳細介紹了JS二分查找算法，具有一定的參考價值，感興趣的小伙伴們可以參考一下
二分法查找，也稱折半查找，是一種在有序數(shù)組中查找特定元素的搜索算法。查找過程可以分為以下步驟：
（1）首先，從有序數(shù)組的中間的元素開始搜索，如果該元素正好是目標元素（即要查找的元素），則搜索過程結(jié)束，否則進行下一步。
（2）如果目標元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半?yún)^(qū)域查找，然后重復(fù)第一步的操作。
（3）如果某一步數(shù)組為空，則表示找不到目標元素。
參考代碼:
// 非遞歸算法
function binary_search(arr, key) {
var low = 0,
high = arr.length - 1;
while(low <= high){
var mid = parseInt((high + low) / 2);
if(key == arr[mid]){
return mid;
}else if(key > arr[mid]){
low = mid + 1;
}else if(key < arr[mid]){
high = mid -1;
}else{
return -1;
}
}
};
var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result = binary_search(arr,10);
alert(result); // 9 返回目標元素的索引值
// 遞歸算法
function binary_search(arr,low, high, key) {
if (low > high){
return -1;
}
var mid = parseInt((high + low) / 2);
if(arr[mid] == key){
return mid;
}else if (arr[mid] > key){
high = mid - 1;
return binary_search(arr, low, high, key);
}else if (arr[mid] < key){
low = mid + 1;
return binary_search(arr, low, high, key);
}
};
var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];
var result = binary_search(arr, 0, 13, 10);
alert(result); // 9 返回目標元素的索引值
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
解決JavaScript頁面刷新與彈出窗口問題2010-03-03
這篇文章主要介紹了JavaScript array常用方法代碼實例詳解,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-09-09
超越Jquery_01_isPlainObject分析與重構(gòu)
isPlainObject是Jquery1.4后提供的新方法,用于判斷對象是否是純粹的對象（通過 {} 或者 new Object 創(chuàng)建的）。2010-10-10
這篇文章主要給大家詳細介紹了JS如何使用鏈式屬性表達式取值和賦值,文章通過代碼示例介紹的非常詳細,對我們的學(xué)習(xí)或工作有一定的幫助,感興趣的同學(xué)可以參考一下2023-08-08
js鎖屏解屏是通過對$.ajax進行封裝實現(xiàn)的,需要的朋友可以參考下2014-07-07
在項目開發(fā)的過程中，為了減少提高性能，減少請求，開發(fā)者往往需要將一些不易改變的數(shù)據(jù)放入本地緩存中。本文就來用JavaScript手寫一個前端存儲工具庫，希望對大家有所幫助2023-02-02
在qq空間，新浪微博，人人網(wǎng)等網(wǎng)絡(luò)平臺大家經(jīng)?？梢钥吹揭绘I分享功能，那么基于js代碼是如何實現(xiàn)一鍵分享的呢？下面腳本之家小編給大家介紹js實現(xiàn)一鍵分享功能的代碼，需要的朋友參考下吧2016-04-04
JS控件autocomplete 0.11演示及下載 1月5日已更新
JS控件autocomplete 0.11演示及下載 1月5日已更新...2007-01-01
本文給大家分享一段實例代碼介紹JS判斷時間段的方法，需要的朋友參考下吧2017-06-06
JavaScript 是一門強大的編程語言,在前端和后端開發(fā)中廣泛使用,生成隨機數(shù)是 JavaScript 開發(fā)中的常見需求,應(yīng)用場景包括游戲開發(fā)、驗證碼生成、數(shù)據(jù)模擬等,本文將詳細介紹 JavaScript 中生成隨機數(shù)的各種方法,并分析其適用場景和優(yōu)缺點,需要的朋友可以參考下2025-03-03