JavaScript實作前端經典演算法二分查找，面試常考喲~
一、二分查找演算法分析
用二分查找演算法查找目標值在陣列中對應的下標
1、二分搜索演算法的前提是一個有序陣列，所以編碼實作的時候，先對它排了個序
2、二分查找就是
（1）劈成兩半，最左邊一個指標low，最右邊一個指標high，最中間一個指標mid
（2）如果查找的目標值小于中間mid對應的值，說明目標值在左邊，那就縮小范圍，把high設定成mid-1
（3）如果查找的目標值大于中間mid對應的值，說明目標值在右邊，那就縮小范圍，把low設定成mid+1
（4）如果查找的目標值就等于中間mid對應的值，那還有啥好說的，直接回傳mid
上圖~
又到了我的拙劣的畫圖環節~
二、編碼實作
細節寫在代碼的注釋里了
Array.prototype.binarySort = function(target) {
// 隨便用什么演算法排，但是二分查找的前提是有序陣列哦
this.quickSort();
let low = 0;
let high = this.length - 1;
while(low <= high) {
const mid = Math.floor((low + high) /2);
const midItem = this[mid];
// 如果查找的目標值小于中間的點
if(target < midItem ) {
// 說明目標值在左半邊，那high指標就是mid的前一位
high = mid - 1;
} else if(target > midItem) {
// 如果目標值在右半邊，那low指標就是mid的后面一位
low = mid + 1;
} else {
// 目標值就是正中間
return mid;
}
}
// 沒找到
return -1;
}
const arr = [1, 5, 9, 3, 18, 6, 2, 7]
console.log(arr.binarySort(9));
這里用了一下快速排序演算法，快速排序演算法思路和實作可見這篇博客
JavaScript實作快速排序演算法
Array.prototype.quickSort = function() {
const rec = (arr) => {
if(arr.length <= 1) return arr;
const base = arr[0];
const left = [];
const right = [];
for(let i = 1; i < arr.length; i += 1) {
if(arr[i] < base) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...rec(left), base, ...rec(right)];
}
const res = rec(this);
res.forEach((item, key) => {
this[key] = item;
});
}
三、時間復雜度
前面博客說過對半劈遞回的是O(logn)，這種對半劈一層回圈的也是O(logn)
寫完啦~~~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/291322.html
標籤：其他
下一篇：JQuery(二)