二分搜索
二分搜索是應用在已排序的陣列中的搜索演算法，其在搜索演算法中的高效體現在其一次排除元資料的一半元素【也正因為要排除一半的元素，所以這個演算法是在排序的陣列中搜索】
- 左指標：指向陣列的起始位置，或者你認為的起始搜索的部分
- 右指標：指向陣列的終止位置，或者你認為的終止搜索部分
- 終止條件：當左指標大于或者等于右指標的時候就結束了
- 找這兩個指標的中間的數
middle，與目標target比較middle > target：說明目標在其左側，那么就將右指標移動到middle - 1位置（注意，這里middle已經比較過了）middle < target：說明目標在其右側，那么就將左指標移動到middle + 1位置（注意，這里middle也已經比較過了）middler === target：說明這個就是目標，那么就回傳位置- 最后沒找到就回傳
-1
function defaultCompareFunction<T>(a: T, b: T){
if(a === b){
return Compare.EQUAL
}
return a > b ? Compare.GREATER : Compare.LESS;
}
export enum Compare {
LESS = -1,
EQUAL = 0,
GREATER = 1
}
function binarySearch<T>(arr:Array<T>, target: T , compareFn: Function = defaultCompareFunction){
let left = 0, // 左指標
right = arr.length - 1; // 右指標
// 回圈結束條件
while(left <= right){
// 中間數
let middle = Math.floor((left + right) / 2);
if(compareFn(arr[middle], target) === Compare.EQUAL){
// 如果相等的話
return middle;
} else if(compareFn(arr[middle], target) === Compare.LESS) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
let index = binarySearch([0,1,2,3,4,5,6,7,8,9,10,12,45], 8);
console.log(index)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/241280.html
標籤：JavaScript
上一篇：vue中路由嵌套的作用
下一篇：vue3.0 mixin 混入