二分搜索
二分搜索是应用在已排序
的数组中的搜索算法,其在搜索算法中的高效体现在其一次排除元数据的一半元素【也正因为要排除一半的元素,所以这个算法是在排序的数组中搜索】
- 左指针:指向数组的起始位置,或者你认为的起始搜索的部分
- 右指针:指向数组的终止位置,或者你认为的终止搜索部分
- 终止条件:当左指针大于或者等于右指针的时候就结束了
- 找这两个指针的中间的数
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)
© 著作权归作者所有
举报
发表评论
0/200