溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
二分查找的前提為：數組、有序。邏輯為：優先和數組的中間元素比較，如果等于中間元素，則直接返回。如果不等于則取半繼續查找。
/**
* 二分查找，遞歸實現。
* @param target
* @param arr
* @param start
* @param end
* @returns {*}
*/
function binarySearch(target,arr,start,end) {
var start = start || 0;
var end = end || arr.length-1;
var mid = parseInt(start+(end-start)/2);
if(target==arr[mid]){
return mid;
}else if(target>arr[mid]){
return binarySearch(target,arr,mid+1,end);
}else{
return binarySearch(target,arr,start,mid-1);
}
return -1;
}
/**
* 有序的二分查找，返回-1或存在的數組下標。不使用遞歸實現。
* @param target
* @param arr
* @returns {*}
*/
function binarySearch(target,arr) {
var start = 0;
var end = arr.length-1;
while (start<=end){
var mid = parseInt(start+(end-start)/2);
if(target==arr[mid]){
return mid;
}else if(target>arr[mid]){
start = mid+1;
}else{
end = mid-1;
}
}
return -1;
}
寫完有序，自然而然的想到了無序的情況如何使用二分查找呢？馬上想到先使用快排分組，分好組再二分。代碼如下：
/**
* 無序的二分查找。返回true/false
* @param target
* @param arr
* @returns {boolean}
*/
function binarySearch(target,arr) {
while (arr.length>0){
//使用快速排序。以mid為中心劃分大小，左邊小，右邊大。
var left = [];
var right = [];
//選擇第一個元素作為基準元素(基準元素可以為任意一個元素)
var pivot = arr[0];
//由于取了第一個元素，所以從第二個元素開始循環
for(var i=1;i<arr.length;i++){
var item = arr[i];
//大于基準的放右邊，小于基準的放左邊
item>pivot ? right.push(item) : left.push(item);
}
//得到經過排序的新數組
if(target==pivot){
return true;
}else if(target>pivot){
arr = right;
}else{
arr = left;
}
}
return false;
}
寫完用快速排序實現的無序二分查找，仔細想了一下該算法的時間復雜度，發現還不如直接一個for循環來得快
以上所述是小編給大家介紹的JavaScript實現二分查找實例代碼，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對億速云網站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
