現(xiàn)如今面試大廠的前端崗位對(duì)于應(yīng)聘者的算法技巧要求越來(lái)越高，現(xiàn)在的前端已經(jīng)不僅僅是制作頁(yè)面就能夠交差的，所以掌握算法技巧是很重要的，下面小千就來(lái)給大家介紹一個(gè)二分查找算法。
二分查找
所謂的算法都不是直接使用關(guān)鍵字indexOf fifindIncludes之類的， 都是原生循環(huán)來(lái)實(shí)現(xiàn)。
二分 就是一拆為2 比如一個(gè)集合：let list = [1,2,3,4,5,6,7]
二分就是在中間拆開(kāi)變成兩個(gè)數(shù)組
list1=[1,2,3,4]
list2 =[5,6,7]
二分用在哪些地方？
主要有有序數(shù)組的查找，但是說(shuō) list= [1.....10] 可能肉眼就知道。但是如果list = [1000,20000] 要找查找某個(gè)數(shù)位置 就觀察不出來(lái)了，更甚至 list = 一千人的電話號(hào)碼 要查找某一個(gè)。二分不是絕對(duì)的性能優(yōu)秀 所有的優(yōu)秀的 都是對(duì)比的。
現(xiàn)在有一個(gè)集合放1到10 要找9的的位置，普通的循環(huán)要找9次 二分找?guī)状文兀?/span>
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
不管開(kāi)頭還是結(jié)尾 還是中間 都穩(wěn)定在 4次之前解決戰(zhàn)斗，同理 100個(gè)數(shù) 找一個(gè)數(shù) 最多7次 40億個(gè)數(shù) 找32次。你學(xué)會(huì)了嗎?
以上就是二分查找算法的介紹了，是不是比你原本使用的方式更好呢？最后歡迎對(duì)前端開(kāi)發(fā)感興趣的同學(xué)來(lái)到千鋒大前端培訓(xùn)班了解我們的前端培訓(xùn)課程，包含算法課程，全程名師面授，現(xiàn)在咨詢還有免費(fèi)前端學(xué)習(xí)資料可以領(lǐng)取，快來(lái)找在線老師了解一下吧。
京公網(wǎng)安備 11010802030320號(hào)