现如今面试大厂的前端岗位对于应聘者的算法技巧要求越来越高，现在的前端已经不仅仅是制作页面就能够交差的，所以掌握算法技巧是很重要的，下面千锋长沙前端培训就来给大家介绍一个二分查找算法。

所谓的算法都不是直接使用关键字indexOf fifindIncludes之类的， 都是原生循环来实现

二分 就是一拆为2 比如一个集合

let list = [1,2,3,4,5,6,7]

二分就是在中间拆开变成两个数组

list1=[1,2,3,4]

list2 =[5,6,7]

二分用在哪些地方 主要有有序数组的查找

但是说 list= [1.....10] 可能肉眼就知道

但是如果list = [1000,20000] 要找查找某个数位置 就观察不出来了

更甚至 list = 一千人的电话号码 要查找某一个

二分不是绝对的性能优秀 所有的优秀的 都是对比的 现在有一个集合放1到10 要找9的的位置

普通的循环要找9次 二分找几次呢

let list = [1,2,3,4,5,6,7,8,9,10]

第一次中间数 5,6都可以 目标数9

假设:

middle =5

target=9

9>5 下次查找的区间 就用二分的后者 [5,6,7,8,9,10]

接着

middle = 7

target = 9

9>7 下次查找的区间 就继续二分为 [7,8,9,10]

继续

middle=8

target=9

9>8 下次查找的区间 [8,9,10]

继续

middle = 9

target= 9

这样就找到9的位置

都是折叠查找 查找的次数比较稳定长度为8的集合 最多3次 就能找到数

log 8=2

就是

同理 16个数 最多需要几次 2 ? = 16 结果是4 最多查找四次

log16= 4

var list = [1,2,3,4,5,6,7,8,9,10];

function search(list,item){

count =1;//计数出现的次数

start = 0;

end = list.length-1;

while(start<=end){

middle =Math.floor((start+end)/2); //取中间下标

console.log(middle);

guess = list[middle];

if(guess==item){

return middle; //返回位置

}

if(guess>item){

end = middle;

}else{

start = middle+1

}

count++;

}

return "查不到";

}

let result = search(list,4);

不管开头还是结尾 还是中间 都稳定在 4次之前解决战斗

同理 100个数 找一个数 最多7次 40亿个数 找32次

上一篇

直播间都有哪些岗位？需要做些什么？

下一篇

千锋长沙前端培训分享之JavaScript中循环遍历JSON响应