現(xiàn)如今面試大廠的前端崗位對(duì)于應(yīng)聘者的算法技巧要求越來越高，現(xiàn)在的前端已經(jīng)不僅僅是制作頁面就能夠交差的，所以掌握算法技巧是很重要的，下面千鋒長(zhǎng)沙前端培訓(xùn)就來給大家介紹一個(gè)二分查找算法。

所謂的算法都不是直接使用關(guān)鍵字indexOf fifindIncludes之類的， 都是原生循環(huán)來實(shí)現(xiàn)

二分 就是一拆為2 比如一個(gè)集合

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

二分就是在中間拆開變成兩個(gè)數(shù)組

list1=[1,2,3,4]

list2 =[5,6,7]

二分用在哪些地方 主要有有序數(shù)組的查找

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

但是如果list = [1000,20000] 要找查找某個(gè)數(shù)位置 就觀察不出來了

更甚至 list = 一千人的電話號(hào)碼 要查找某一個(gè)

二分不是絕對(duì)的性能優(yōu)秀 所有的優(yōu)秀的 都是對(duì)比的 現(xiàn)在有一個(gè)集合放1到10 要找9的的位置

普通的循環(huán)要找9次 二分找?guī)状文?/p>

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

第一次中間數(shù) 5,6都可以 目標(biāo)數(shù)9

假設(shè):

middle =5

target=9

9>5 下次查找的區(qū)間 就用二分的后者 [5,6,7,8,9,10]

接著

middle = 7

target = 9

9>7 下次查找的區(qū)間 就繼續(xù)二分為 [7,8,9,10]

繼續(xù)

middle=8

target=9

9>8 下次查找的區(qū)間 [8,9,10]

繼續(xù)

middle = 9

target= 9

這樣就找到9的位置

都是折疊查找 查找的次數(shù)比較穩(wěn)定長(zhǎng)度為8的集合 最多3次 就能找到數(shù)

log 8=2

就是

同理 16個(gè)數(shù) 最多需要幾次 2 ? = 16 結(jié)果是4 最多查找四次

log16= 4

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

function search(list,item){

count =1;//計(jì)數(shù)出現(xiàn)的次數(shù)

start = 0;

end = list.length-1;

while(start<=end){

middle =Math.floor((start+end)/2); //取中間下標(biāo)

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);

不管開頭還是結(jié)尾 還是中間 都穩(wěn)定在 4次之前解決戰(zhàn)斗

同理 100個(gè)數(shù) 找一個(gè)數(shù) 最多7次 40億個(gè)數(shù) 找32次

上一篇

直播間都有哪些崗位？需要做些什么？

下一篇

千鋒長(zhǎng)沙前端培訓(xùn)分享之JavaScript中循環(huán)遍歷JSON響應(yīng)